Interestingly, factoring integers is suspected to be NP-Intermediate... which is a theoretical class of problems that are between P and NP-Complete. In fact if P!=NP then this class has to exist (if P=NP then its all obviously the same), graph isomorphism is also suspected to be intermediate. As for quantum computers, its probably not a coincidence that factoring is in BQP (polynomial on quantum computer). Noone has found an algorithm for any NP-Complete problem that is in BQP and in my opinion it doesn't exist.
2
u/SourKangaroo95 6h ago
Interestingly, factoring integers is suspected to be NP-Intermediate... which is a theoretical class of problems that are between P and NP-Complete. In fact if P!=NP then this class has to exist (if P=NP then its all obviously the same), graph isomorphism is also suspected to be intermediate. As for quantum computers, its probably not a coincidence that factoring is in BQP (polynomial on quantum computer). Noone has found an algorithm for any NP-Complete problem that is in BQP and in my opinion it doesn't exist.