What is the relation between P vs. NP and Nature's ability to solve NP problems efficiently?

Question

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)?

Answer 1

Here are five remarks that might be helpful to you:

1. 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.

2. 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.

3. 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.

4. 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 )

5. 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

Answer 2

this question is basically asking about the field of natural computing which has many interesting angles/directions. here's a nice survey article: Fundamentals of natural computing: an overview by de Castro.

also these areas are basically open questions in the field of computing and physics and subject to an inherent "uncertainty principle" in that they may conceivably never be definitively answered for various reasons. there are many different physical computation systems, new ones are discovered over time (eg DNA computing is a relatively young area), and we cant be sure that we've found them all [and from experience/history its unlikely that we have].

also the extreme limits of physics are applicable [eg wrt black holes etc] and these stretch the theories of physics to the limits! (see eg "what is the volume of information") theoretical physicists generally acknowledge that there are aspects of physical reality that are not covered by human knowledge and [mathematical] models esp at the extremes.

there are some strongly held/defended, possibly unprovable beliefs however among researchers such that they might be called "theses" in the same sense of the Church-Turing thesis.[1] some authorities refer to a "polynomial-time" Church-Turing thesis related to your question(s). there are also references to the Strong CT thesis:

any computing device can be simulated by TMs with at worst a polynomial slowdown.

or the Extended CT thesis [Parberry] [3]:

Time on all "reasonable" machine models is related by a polynomial.

in short the research and writing in this general area is not settled; its active/ongoing and subject to high controversy. there is some reference on wikipedia[4] but otherwise have not seen a nice survey article on the subject, only many different papers that tend to advocate certain points of view. also note there is very strong current debate/controversy in QM computing field on feasibility (wrt inherent noise) & viability etc.[5]

[1] Physics and the Church-Turing thesis mathoverflow

[2] what would it mean to disprove the CT thesis cstheory.se

[3] extended CT thesis cstheory.se

[4] Church-Turing thesis variations, wikipedia

[5] State of the art and prospects for QM computing Dyakonov

Answer 3

I had a neural computation professor once that pointed out an excellent example of how "analog" techniques could be used on embarrassingly parallel problems to reduce the asymptotic bound of a computation:

Take a bundle of sticks of different sizes. There are many algorithmic ways to sort that bundle of sticks from longest to shortest with O(n*log(n)). An "analog" way to sort that bundle of sticks would be to stand them on end and let the sticks rest one end on a table (1 step). Now you have all the sticks with one end at the same level against the table. Take your hand and place it on top -- it will hit the longest, remove that stick and repeat for N steps. This process is O(N + 1) which is O(N). The key here was stacking the sticks on end -- a massively parallel solution to order the other ends of the sticks along the z-axis (up).

This is a neat thought experiment and can give an idea how analog solutions can reduce the asymptotic bound of an algorithm in a simple manner. Two huge caveats here:

1) We haven't taken an NP problem to a P problem with this example (more on that later) and

2) if you used N processors to sort N items you could sort the numbers in O(log n) time (with a big constant), so the reduction is not magical. Sometimes the analog resources needed solve a problem in a highly parallel manner are cheap. Another example of a cheap resource would be neurons (biological) for complex learning and pattern recognition.

Neurons can also put the apparent NP => P into perspective. NP problems are NP to find the optimal solution. You can find a "good enough" solution in P time that will work fine in nature. Evolution selects for highly efficient solutions that are "good enough". Think about how good the average person is at identifying objects in almost O(1) time. That's because there is a lot of parallel processing going on, and your brain still doesn't always come up with the optimal solution. For example, optical illusions, or forgetting where you put your keys (which would easily be O(1) for a computer!).

Another point with NP vs P in nature: solving NP to find the optimal solution is not the same as identifying the optimal solution. Identification of an optimal solution to an NP problem can be done in P time. Again recognition of a "good enough" solution will work rather than an optimal solution. Take the example of protein folding -- this is an example of nature doing all of the above. It takes advantage of molecular interaction forces that all work in parallel (no need for the natural folding "algorithm" to address one atom at a time as a computational algorithm does). Also, there is no guarantee that the (functionally) optimal solution to the protein folding will be found.

There are many examples of diseases due to protein misfolding. As @PeterShor pointed out sometimes the "natural" algorithm doesn't work at all (leading to a thermodynamically optimal solution, but not a functional one). That is where chaperone proteins come in -- they guide the folding into the correct functional form (a thermodynamic local minimum). Correctly formed proteins also interact with other proteins for transport to the right location so the "bad" ones (where the heuristic algorithm didn't actually solve the NP problem) are often degraded without being transported anywhere. All of these transports and folding mechanisms are happening with massive parallel pipes. Multiple transcription and processing mechanisms are simultaneously converting DNA->RNA->Protein at different points on a gene sequence. Every cell in your body is doing the same (but with different chemical messages about what to produce).

So, in short: How does nature do it? Tricks and Parallelism. Generally it's not actually turning an NP problem into P, it's just making it look easy.