Hacker News new | past | comments | ask | show | jobs | submit login

[deleted]



Integer factoring is not (known to be) NP hard, i.e. we don't know whether we can reduce any NP problem to integer factoring (we suspect we cannot). On the other hand, it's in the intersection of NP and Co-NP, because you can give an effectively checkable proof of both primality and compositeness. If you're interested to learn more about these things, Scott Aaronson has an equivalent of a complexity course stuffed into one lecture here ;)

http://www.scottaaronson.com/democritus/lec6.html


Factoring can be polynomial even if P!=NP.




Consider applying for YC's W25 batch! Applications are open till Nov 12.

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

Search: