Linked by Hadrien Grasland on Sun 23rd Jan 2011 17:30 UTC, submitted by fran
Permalink for comment 459465
To read all comments associated with this story, please click here.
To read all comments associated with this story, please click here.
Features
Linked by David Adams on 05/16/13 4:23 UTC
Linked by Thom Holwerda on 05/11/13 21:41 UTC
Linked by Thom Holwerda on 05/08/13 14:22 UTC
Linked by Thom Holwerda on 05/02/13 15:28 UTC
Linked by Thom Holwerda on 04/29/13 21:06 UTC
Linked by Thom Holwerda on 04/24/13 22:24 UTC
Linked by Thom Holwerda on 04/18/13 11:21 UTC
Linked by Thom Holwerda on 04/16/13 9:29 UTC
Linked by Thom Holwerda on 04/15/13 22:44 UTC
Linked by Thom Holwerda on 04/14/13 18:22 UTC, submitted by MOS6510
More Features »
Sponsored Links



Member since:
2005-07-07
The proof of P=NP does not depend on the speed or parallelism of the computer. Today, you can solve some NP problems very fast, esp. using FPGAs, with careful mapping. It is the "careful mapping" part which is also pertinent to quantum computers, and which makes the proof still elusive.
It's not a matter of speed, but of complexity. If it is always O(1) to look at all branches of a solution path simultaneously (as it is in theory with a quantum computing device), then NP problems can be solved in P time on a quantum computing device. In essence, quantum computing simulates non-determinacy in that instead of an oracle function revealing the correct path, all paths are considered simultaneously (without increasing the complexity).