3 ms·

I did mean subset, apparently a quantum computer could not solve every NP-complete problem in polynomial time. factorisation seems to be one of the candidates t

I did mean subset, apparently a quantum computer could not solve every NP-complete problem in polynomial time. factorisation seems to be one of the candidates to benefit from quantum computation (thanks to Shor's algorithm), but SAT (for instance) would not, at least based on current state-of-art

eru 14y ago
Yes, I know. So I guess if you meant subset, then you didn't mean to write "quantum ___non-deterministic___ Turing machine in P-time"?