Re:Why now is the best time to study quantum computing (2014)
by PeCaN on Sunday May 01, 2016 @01:52PM
(#11607095)
No, he means all problems without a (known) polynomial time solution.
[ Parent
| on HN ]
Re:Why now is the best time to study quantum computing (2014)
by lorenzhs on Sunday May 01, 2016 @02:18PM
(#11607231)
As ikeboy implied, NP does not stand for non-polynomial, but for non-deterministic polynomial. Thus the open question whether the two are equal. In particular, it is clear that P is a subset of NP, as any problem that is polynomially computable with a deterministic machine is immediately also polynomially computable with a non-deterministic one by just not using the non-determinism