Re:Why now is the best time to study quantum computing (2014)
by ikeboy on Sunday May 01, 2016 @01:40PM
(#11607047)
You mean NP-complete, right?
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.
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
Not at all. As it is believed currently, there are a few problems (BQP space) such as the discreet logarithm that quantum computers can solve quickly. But lots of other hard problems, probably including all NP problems, cannot be solved exponentially faster by a quantum computer.
See also http://security.stackexchange.com/questions/48022/what-kinds...