NP-complete Problems and Physical Reality - 2005
Details
Title : NP-complete Problems and Physical Reality Author(s): Aaronson, Scott Link(s) : http://arxiv.org/abs/quant-ph/0502072
Rough Notes
Starts with a critique of Horgan's "End of Science" with the argument that we only learnt about being able to factor integers in polynomial time via quantum computers in the past decade.
An important question arises : Can NP-complete problems be solved in polynomial time using the resources of the physical universe? Author argues that the presumed intractability of NP-complete problems can be taken as a useful constrain in the search for new physical theories. To support this, unusual computing proposals are surveyed.
Examples
Soap bubbles
Given a set of points in a Euclidean plane, find a Steiner tree which is a collection of line segments of minimum total length (the line segments can meet at vertices called Steiner vertices) is NP-hard. Meanwhile, if 2 glass plates with pegs between are dipped in soapy water, the soap bubbles form a Steiner tree connecting the pegs in a minimum-energy configuration (according to CS folklore apparently). However this does not mean we can do this physical experiment to find Steiner trees, since there is not reason to believe that the desired configuration is reached in general. The author performed his own experiment and found that the optimum was not always found.
Protein folding is more interesting since its likely that they evolves to not have local optima. A protein that folded in unpredictable ways would put the organism which relied on it at an adaptive disadvantage - this does happen e.g. with prions. Hence even if we somehow constructed a protein which represents a hard 3SAT instance, there is no reason for it to fold as well as naturally occurring proteins.