36 ms·
I was under the impression that QNP (the class of problems solvable by a quantum non-deterministic Turing machine in P-time) is a (non strict) subset of NP. Thi
by tiziano88 14y ago
I was under the impression that QNP (the class of problems solvable by a quantum non-deterministic Turing machine in P-time) is a (non strict) subset of NP. Things might have changed since I last checked though.
- eru 14y agoDid you mean superset instead of subset? Anyway for my statement I was only interested deterministic polynomial time (perhaps with access to randomness) with or without quantum capabilities. "Why Philosophers Should Care About Computational Complexity" (http://arxiv.org/abs/1108.1791v3 http://arxiv.org/abs/1108.1791v3) is a good read about this---amongst other things.
- tiziano88 14y agoI 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 agoYes, I know. So I guess if you meant subset, then you didn't mean to write "quantum ___non-deterministic___ Turing machine in P-time"?