Linked by Hadrien Grasland on Sun 23rd Jan 2011 17:30 UTC, submitted by fran
Thread beginning with comment 459469
To view parent comment, click here.
To read all comments associated with this story, please click here.
To view parent comment, click here.
To read all comments associated with this story, please click here.
But by proving that NP=P is the only way you can substantiate claims that an NP problem can be solved in P time using Quantum computers. Which was the gist of the discussion we've been having.
Quantum computer may help make part of an NP computation deterministic, but that does not mean that NP problems become deterministic in the least.
RE[8]: Niche product?
by GeorgesBraque on Sun 23rd Jan 2011 22:53
in reply to "RE[7]: Niche product?"
But by proving that NP=P is the only way you can substantiate claims that an NP problem can be solved in P time using Quantum computers. Which was the gist of the discussion we've been having.
Quantum computer may help make part of an NP computation deterministic, but that does not mean that NP problems become deterministic in the least.
Quantum computer may help make part of an NP computation deterministic, but that does not mean that NP problems become deterministic in the least.
P time is not the same as the class P.
P time means solvable in polynomial time.
The class P is the set of problems solvable in polynomial time on a deterministic machine. The class NP is the set of problems solvable in polynomial time on a non-deterministic machine.
NP problems are often O(N!) or O(N^N) or worse on deterministic machines. However, they most likely are solvable in P time on quantum computing machines. This does NOT mean that P=NP because quantum computing machines are NOT deterministic.





Member since:
2005-07-07
Which is why I said that the speed of the computer is irrelevant when trying to prove that P=NP.
I think that quantum computing cannot ever apply to proving P=NP or P!=NP because complexity theory is predicated on running programs on deterministic machines. Quantum machines would be non-deterministic.
Also, just for fun, check this out (if you haven't already):
http://science.slashdot.org/story/11/01/21/2047229/Eulers-Partition...