4 ms·
That is true, but integer factorization is not an NP-hard problem, as far as we know at least. A quantum algorithm, Shor's algorithm, is indeed known to be able
by tsimionescu 4y ago
That is true, but integer factorization is not an NP-hard problem, as far as we know at least. A quantum algorithm, Shor's algorithm, is indeed known to be able to solve it in polynomial time if you have a QC.
It is suspected to be NP but not even NP-complete, nevermind NP-hard. It is suspected not to be in P, but that is not yet proven.
- kragen 4y agoInteger factorization is obviously in NP, though as you say, whether it is in the P subset of NP is still an open question.
- tsimionescu 4y agoI was trying to be careful with my language specifically to avoid this mistake, but I still messed up...
- kragen 4y agoIt's tricky!