principleMajor
What is the relation between P vs. NP and Nature's ability to solve NP problems efficiently?
Viewed 0 times
efficientlythewhatnaturebetweensolveandproblemsrelationability
Problem
I was thinking about how nature can efficiently compute ridiculous (i.e. NP) problems with ease. For example, a quantum system requires a $2^n$ element vector to represent the state, where $n$ is just the number of particles. Nature doesn't need any extra time despite the exponential nature of "solving" this $n$-particle system.
This may not be a wholly valid assumption, but the action principle in physics makes me think that nature always wants to do things the easiest way. If that's not true, then this question is probably moot.
If we found that nature was NOT capable of solving some problems efficiently, does this mean we are doomed in terms of being able to solve NP problems in polynomial time? Are the laws of physics a strong enough weapon for tackling P vs. NP? Is the converse of the first question/assertion also true (if nature can do it, then there must be a way for us to as well)?
This may not be a wholly valid assumption, but the action principle in physics makes me think that nature always wants to do things the easiest way. If that's not true, then this question is probably moot.
If we found that nature was NOT capable of solving some problems efficiently, does this mean we are doomed in terms of being able to solve NP problems in polynomial time? Are the laws of physics a strong enough weapon for tackling P vs. NP? Is the converse of the first question/assertion also true (if nature can do it, then there must be a way for us to as well)?
Solution
Here are five remarks that might be helpful to you:
-
The current belief is that, despite the exponentiality of the wavefunction, quantum mechanics will not let us solve NP-complete problems in polynomial time (though it famously does let us solve certain "special" NP problems, like factoring and discrete logarithms). The basic difficulty is that, even if a solution to an NP problem is "somewhere" in the wavefunction, that isn't useful if a measurement will only reveal that solution with exponentially-small probability. To get a useful quantum algorithm, you need to use quantum interference to make the correct answer observed with high probability, and it's only known how to get an exponential speedup that way (compared to the best-known classical algorithm) for a few special problems like factoring.
-
The action principle doesn't imply that Nature has any magical minimization powers. The easiest way to see that is that any physical law formulated in terms of the action principle, can also be formulated in terms of the ordinary time-evolution of a state, without reference to anything being minimized.
-
If P=NP, then certainly NP-complete problems can be solved in polynomial time in the physical universe, since universal Turing computers exist (you're using one now). However, the converse direction is far from obvious! For example, even if you assume P≠NP, it's still logically possible (if very unlikely) that quantum computers could solve NP-complete problems in polynomial time.
-
The mere assumption that there are some problems that we can't solve efficiently, certainly doesn't imply that NP-complete problems have to be among those problems! (Maybe it will turn out that quantum gravity lets us solve NP-complete problems in linear time, but the PSPACE-complete problems still take exponential time... :-D )
-
For whatever it's worth, my money is firmly on the conjecture not only that P≠NP, but also that NP-complete problems are intractable in the physical universe---using quantum computers, analog computers, "black hole computers," or any other resource. For more about my reasons why, you might enjoy my old survey article NP-complete Problems and Physical Reality
-
The current belief is that, despite the exponentiality of the wavefunction, quantum mechanics will not let us solve NP-complete problems in polynomial time (though it famously does let us solve certain "special" NP problems, like factoring and discrete logarithms). The basic difficulty is that, even if a solution to an NP problem is "somewhere" in the wavefunction, that isn't useful if a measurement will only reveal that solution with exponentially-small probability. To get a useful quantum algorithm, you need to use quantum interference to make the correct answer observed with high probability, and it's only known how to get an exponential speedup that way (compared to the best-known classical algorithm) for a few special problems like factoring.
-
The action principle doesn't imply that Nature has any magical minimization powers. The easiest way to see that is that any physical law formulated in terms of the action principle, can also be formulated in terms of the ordinary time-evolution of a state, without reference to anything being minimized.
-
If P=NP, then certainly NP-complete problems can be solved in polynomial time in the physical universe, since universal Turing computers exist (you're using one now). However, the converse direction is far from obvious! For example, even if you assume P≠NP, it's still logically possible (if very unlikely) that quantum computers could solve NP-complete problems in polynomial time.
-
The mere assumption that there are some problems that we can't solve efficiently, certainly doesn't imply that NP-complete problems have to be among those problems! (Maybe it will turn out that quantum gravity lets us solve NP-complete problems in linear time, but the PSPACE-complete problems still take exponential time... :-D )
-
For whatever it's worth, my money is firmly on the conjecture not only that P≠NP, but also that NP-complete problems are intractable in the physical universe---using quantum computers, analog computers, "black hole computers," or any other resource. For more about my reasons why, you might enjoy my old survey article NP-complete Problems and Physical Reality
Context
StackExchange Computer Science Q#11026, answer score: 21
Revisions (0)
No revisions yet.