Re:What if P = NP?
by dcosson on Friday April 01, 2011 @02:35PM
(#2397432)
"Hello World" isn't a decision problem, but I see your point. However NP-Complete (and by extension NP-Hard) and P are distinct classes of problems, http://en.wikipedia.org/wiki/NP-complete so my statement that factorization is not an NP-Hard problem is true (unless, of course, P=NP).
Either way, my point was that there are systems (i.e. quantum computers) that can factor numbers efficiently, but it is still widely believed that true NP-Complete and NP-Hard problems cannot be solved efficiently even with such systems.
Either way, my point was that there are systems (i.e. quantum computers) that can factor numbers efficiently, but it is still widely believed that true NP-Complete and NP-Hard problems cannot be solved efficiently even with such systems.