Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

or perhaps he can break RSA in polynomial time or something like that


Pretty sure that's the same thing as proving P=NP.


No it's not. The factoring problem/RSA problem have never been proven to be NP-complete. Shor's algorithm shows that it's NP, but not NP-complete (or hard). I think it's also in co-NP.


[deleted]


Yeah.... but like he said, RSA being in P does not imply that P=NP because RSA has not be shown (and isn't believed) to be NP-complete. If P=NP, then RSA would of course be in P.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: