On: Quantum winter is coming

[tsimionescu]

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 → tsimionescu]

Integer factorization is obviously in NP, though as you say, whether it is in the P subset of NP is still an open question.

[tsimionescu → kragen]

I was trying to be careful with my language specifically to avoid this mistake, but I still messed up...

[kragen → tsimionescu]

It's tricky!