News for hackers. Stuff that matters.
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
Re:Why now is the best time to study quantum computing (2014) by ikeboy on Sunday May 01, 2016 @01:57PM (#11607126)
That's still not NP, that's NPI+NP-complete.
Re:Why now is the best time to study quantum computing (2014) by dcosson on Wednesday May 04, 2016 @11:25PM (#11633832)
Yeah, NP-complete.