7
$\begingroup$

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

$\endgroup$

migrated from cstheory.stackexchange.com Apr 4 '13 at 19:06

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 12
    $\begingroup$ nature can efficiently compute ridiculous (i.e. NP) problems with ease — [citation needed] $\endgroup$ – JeffE Mar 30 '13 at 22:11
  • $\begingroup$ Fair point, I'm probably not using the right terminology to describe what I'm thinking (or I don't understand the concept.. or both). I'm open to being corrected and enlightened. Thanks. $\endgroup$ – hadsed Mar 31 '13 at 2:21
  • $\begingroup$ ps: I think answers to this question also apply to your question. $\endgroup$ – Kaveh Mar 31 '13 at 17:38
  • 5
    $\begingroup$ Nature can't solve protein folding with ease ... it needs help. Look up molecular chaperones. $\endgroup$ – Peter Shor Apr 1 '13 at 20:51
  • $\begingroup$ There is evidence that such intuition is misleading because it is based on small problem instances and Nature's solution doesn't always scale well asymptotically. Soap bubbles seemed to solve small optimization problems, but get stuck in local minimal at scale. $\endgroup$ – Vijay D Apr 5 '13 at 7:23
21
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Thanks for responding Scott, I know my question wasn't very well formed (mostly due to ignorance). Your comments are helpful as a starting point for further reading and research, and thanks for linking that paper (it's actually answering a lot of sub-questions I'd also been having). $\endgroup$ – hadsed Mar 31 '13 at 2:25
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ see also the comprehensive and heavily citationed Computation in Physical Systems, Stanford encyclopedia of philosophy $\endgroup$ – vzn Apr 5 '13 at 4:26
  • $\begingroup$ the good news is that the universe and physics is highly conducive to computation, and some believe this in a very strong way such that its thought the universe and physics itself is algorithmic, or an algorithm, the so-called digital physics scenario. this originates with Fredkin with further development by Wolfram and can also be seen in QM perspectives eg Wheeler "it from bit". $\endgroup$ – vzn Apr 5 '13 at 4:36
  • $\begingroup$ more evidence for incomplete physical theories by humans— the crucial Higgs particle which is taken as analogous to underlying glue of the universe was only recently confirmed after decades of speculation/research, massive teams of scientists, and over $15B spent on the largest scientific experiment ever constructed. $\endgroup$ – vzn Apr 5 '13 at 5:00
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The problem with analog computation is precision. If you allow arbitrary real numbers as stick lengths, you won't be able to correctly distinguish sticks using your hands. On the other hand (heh), discretizing problems often makes them easier on digital computers too, see for example radix sort. I also don't think it is useful to use Big-Oh when talking about brains. The input size is bounded, everything is O(1). Recognizing Waldo in a crowded picture takes longer than on blank backgrounds anyway... $\endgroup$ – adrianN Apr 5 '13 at 9:09
  • $\begingroup$ Well, of course that wasn't meant to be a rigorous engineering example (see paper by @ScottAaronson, scottaaronson.com/papers/npcomplete.pdf for physical limits). It was an example of how analog resources can be highly parallel for cheap. Regarding the "Big Oh" of brains: The OP was curious about seemingly "efficient computation of NP problems". I think you are supporting the point I was trying to make about Big Oh and the brain: NP problems aren't being solved by the brain, its just heuristics approximations -- so much so that it sometimes fails at O(1) problems. $\endgroup$ – dhj Apr 5 '13 at 17:08
  • $\begingroup$ @dhj Thank you for this exposition, I think it answers a lot of underlying questions I've been having. If I had rep, I'd give an upvote. $\endgroup$ – hadsed Apr 5 '13 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy