# Intractability of NP-complete problems as a principle of physics?

I'm always intrigued by the lack of numerical evidence from experimental mathematics for or against the P vs NP question. While the Riemann Hypothesis has some supporting evidence from numerical verification, I'm not aware of similar evidence for the P vs NP question.

Additionally, I'm not aware of any direct physical world consequences of the existence of undecidable problems (or existence of uncomputable functions). Protein folding is NP-complete problem but it appears to be taking place very efficiently in biological systems. Scott Aaronson proposed using the NP Hardness Assumption as a principle of physics. He states the assumption informally as "NP-complete problems are intractable in the physical world".

Assuming NP Hardness Assumption, Why is it hard to design a scientific experiment that decides whether our universe respects the NP Hardness Assumption or not?

Also, Is there any known numerical evidence from experimental mathematics for or against $P\ne NP$?

EDIT: Here is a nice presentation by Scott Aaronson titled Computational Intractability As A Law of Physics

• Here is a related observation, according to Quantum theory, every physical quantity is discrete including time, length, mass and energy (extremely small). So, Is correct to view the evolution of a quantum system as a discrete optimization problem governed by the principle of least action over all possible state space trajectories? – Mohammad Al-Turkistany Sep 24 '10 at 14:58
• The fact that proteins fold well in vivo should not be taken as evidence that the universe is solving NP-complete problems. Proteins have evolved to fold themselves efficiently. There are even some proteins that will fold well in the cellular environment which don't fold properly in vitro. This is because in the cell, there are other proteins called chaperonins which assist in the folding process (these chaperonins presumably co-evolved with the proteins that they help fold). – Peter Shor Nov 2 '10 at 22:12

I don't think that the fact that $P\neq NP$ is an asymptotic statement is an automatic "dealbreaker". One can make concrete conjectures that are consistent with our knowledge but stronger than P vs NP such as "It takes at least $2^{n/10}$ steps to find a satisfying assignment for a random n variable 10SAT formula" (with "random" being e.g., the planted model of Achlioptas Coja-Oghlan, this is just an example - I don't know what are reasonable concrete numbers offhand).

Such conjecture can result in a refutable prediction that any natural system that will try to solve this will fail (e.g., get stuck in a local minima), something you can verify with experiments. Indeed, I'm not an expert on this but to my knowledge, as Joe Fitzsimons mentioned, such predictions had been confirmed with Adiabatic computing. (Scott Aaronson also had some entertaining experiments with soap bubbles.)

Of course you can also see some "empirical evidence" for $P \neq NP$ in the fact that people have been trying to solve optimization problems, cryptoanalyze encryptions, etc.. and haven't been successful so far...

• @Jeff - I think this is evidence that P is not equal to NP in the same way that the fact that all numbers we have tried so far have followed Goldbach's Conjecture is evidnece in favor of Goldbach's Conjecture and not just in favor of us picking the wrong numbers. – Vinayak Pathak Sep 19 '10 at 2:32
• Boaz: I might be willing to accept it as evidence for the weaker hypothesis "THIS algorithm needs at least $2^{n/10}$ steps", but not for the stronger hypothesis "ANY algorithm needs at least $2^{n/10}$ steps." There are just too many (in fact, infinitely many) untried algorithms, or even classes of algorithms, for me to accept that any experimenter has tried a representative sample. – Jeffε Sep 19 '10 at 4:13
• If you could somehow show Levin's universal search algorithm needs $2^{n/10}$ steps then you show any algorithm needs effectively this many... of course given our current knowledge this would be insanely impractical to implement and test. – Ryan Williams Sep 19 '10 at 19:11
• Ryan - in practice you'd only be able to enumerate over programs with very tiny description size. (See also Luca Trevisan's paper - eccc.hpi-web.de/report/2010/034/download) – Boaz Barak Sep 20 '10 at 1:40
• JeffE - suppose that some evidence from some other scientific field suggests a natural system may reach quickly its global minimum, while the (strengthened) $P\neq NP$ assumption predicts it gets stuck at a local minimum, and it turns out the latter is true. That seems to me to be at least some evidence to $P\neq NP$. It's not conclusive evidence, but as these things accumulate, if it turns out (strengthened) $P\neq NP$ has positive predictive power, that is an argument for making it a "law of nature". (That holds to at least all algorithms/natural systems we've encountered so far...) – Boaz Barak Sep 20 '10 at 1:50

The real world is a constant-sized object, so there's no way to rule out a polynomial-time real world procedure to solve NP-complete problems that have a huge constant hidden in the big O notation.

Anyway, besides this point, the assumption is a statement of the form "there is no real world procedure that does ..." How does one design an experiment to refute such a statement? If the assumption was something like "If we do X in the real world, Y happens," then this can be refuted by performing X. The statement that we want asserts the non-existence of something, so I can't see an experiment deciding it. It could be shown as a physical consequence of the laws of physics, but this is even harder than P vs NP, because a Turing machine does follow the laws of physics. Since we've been unsuccessful even at showing that TMs cannot solve NP-complete problems in polynomial time, it seems completely hopeless to show that no physical process can solve NP-complete problems in polynomial time.

• If the real world is a constant-size object, then all computers built to date are finite automata. – Peter Shor Jul 25 '13 at 0:23

Indeed the physical version of P not equal to NP, namely that no natural physical systems can solve NP complete problem is very interesting. There are a few concerns

1) The progrem seems practically "orthogonal" to both experimental and theoretical physics. So it does not really provide (so far) useful insights in physics.

There are some nice arguments how one can deduce from this physical version of the conjecture some insights in physics, but these arguments are fairly "soft" and have loopholes. (And such arguments are likely to be problematic, since they rely on very difficult mathematical conjectures such as NP nonot equal to P, and NP not being included in BQP that we do not understand.)

(A similar comment apply to the "Church-turing thesis".)

2) Although the physical NP not equal P is a wider conjecture than the mathematical NP not equal P, we can also regard it as more restricted since the algorithms that occur in nature (and even the men-made algorithms) seem to be a very restricted class of all theoretically possible algorithms. It will be very interesting to understand such restrictions formally, but in any case any exerimental "proof" as suggested in the question will apply only to these restricted class.

3) In scientific modeling, computational complexity represents a sort of a second order matter where first we would like to model a natural phenomena and see what can be predicted based on the model (putting computational complexity theory aside). Giving too much weight to computational complexity issues in the modeling stage does not seem to be fruitful. In many cases, the model is computationally intractable to start with but it may still be feasible for naturally occuring problems or useful to understand the phenomena.

4) I agree with Boaz that the asymptotic issue is not necessary a "deal breaker". Still it is a rather serious matter when it comes to the relevance of computational complexity matters to real life modeling.

If you'll allow me to generalize a tiny bit... Let's extend the question and ask for other complexity-theoretic hardness assumptions and their consequences for scientific experiments. (I'll focus on physics.) Recently there was a rather successful program to try to understand the set of allowable correlations between two measurement devices which, while spatially separated, perform a measurement on a (possibly non-locally correlated) physical system (1). Under this and similar setups, one can use the assumptions about the hardness of communication complexity to derive tight bounds which reproduce the allowable correlations for quantum mechanics.

To give you a flavor, let me describe an earlier result in this regard. A Popescu-Rohrlich box (or PR box) is an imaginary device which reproduces correlations between the measurement devices which are consistent with the principle that no information can travel faster than light (called the principle of no signaling).

S. Popescu & D. Rohrlich, Quantum nonlocality as an axiom, Found. Phys. 24, 379–385 (1994).

We can see this as an instance of communication complexity having some influence. The idea that two observers must communicate implicitly assumes some constraint which a physicist would call no signaling. Turning this idea around, what types of correlations are possible between two measurement devices constrained by no signaling? This is what Popescu & Rohrlich study. They showed that this set of allowable correlations is strictly larger than those allowed by quantum mechanics, which are in turn strictly larger than those allowed by classical physics.

The question then presents itself, what makes the set of quantum correlations the "right" set of correlations, and not those allowed by no signaling?

To address this question, let's make the bare-bones assumption that there exist functions for which the communication complexity is non-trivial. Here non-trivial just means that to jointly compute a boolean function f(x,y), it takes more than just a single bit (2). Well surprisingly, even this very weak complexity-theoretic assumption is sufficient to restrict the space of allowable correlations.

G. Brassard, H. Buhrman, N. Linden, A. A. Méthot, A. Tapp, and F. Unger, Limit on Nonlocality in Any World in Which Communication Complexity Is Not Trivial, Phys. Rev. Lett. 96, 250401 (2006).

Note that a weaker result was already proven in the Ph.D. thesis of Wim van Dam. What Brassard et al. prove is that having access to PR boxes, even ones which are faulty and only produce the correct correlation some of the time, enables one to completely trivialize communication complexity. In this world, every two-variable Boolean function can be jointly computed by transmitting only a single bit. This seems pretty absurd, so let's look at it conversely. We can take the non-triviality of communication complexity as an axiom, and this allows us to derive the fact that we don't observe certain stronger-than-quantum correlations in our experiments.

This program using communication complexity has been surprisingly successful, perhaps much more so than the corresponding one for computational complexity. The papers above are really just the tip of the iceberg. A good place to begin further reading is this review:

H. Buhrman, R. Cleve, S. Massar and R. de Wolf, Nonlocality and communication complexity, Rev. Mod. Phys. 82, 665–698 (2010).

or a forward literature search from the two other papers that I cited.

This also raises the interesting question about why the communication setting seems much more amenable to analysis than the computation setting. Perhaps that could be the subject of another posted question on cstheory.

(1) Take for example the experiments measuring something known as the CHSH inequality (a type of Bell inequality), where the physical system consists of two entangled photons, and the measurements are polarization measurements on the individual photons at two spatially distant locations.

(2) This single bit is necessary whenever f(x,y) actually depends on both x and y, since sending zero bits would violate no signaling.

Also, Is there any known numerical evidence from experimental mathematics for or against $P \neq NP$?

Not as far as I know. However, one could get numerical evidence against $NP \subseteq P/poly$ of a similar sort of that found for the Riemann Hypothesis or Goldbach conjecture, by using explicit computations to show that, say, SAT up to length 10 does not have circuits of size 20 (where you let the values of 10 and 20 vary). This still runs into the same issue raised in the other answers -- finite evidence cannot give us an asymptotic answer. But essentially the same issue is true for the current "evidence" for the Riemann Hypothesis.

Now, finding a minimum circuit for SAT up to length 10 is currently very difficult. However, some of the ideas in geometric complexity theory allow you to get similar results with a more efficient (I think only exponential instead of doubly-exponential) computational search. One of Mulmuley's conjectures is that in fact this search can be done in polynomial time, but we are a long way from proving anything close to that.

• Could you elaborate more on how you can use GCT to improve upon the brute force search? – arnab Sep 19 '10 at 18:59
• @arnab, answering your question in a sense goes to the heart of GCT, which would be difficult in the space of a comment :). The gist is that certain representations of $GL_n$ can be certificates of hardness. As irreducible rep'ns of $GL_n$ are labelled by partitions with at most n parts, the question (not quite, but more or less) is to determine whether or not a given partition corresponds to a rep'n that has the rep'n-theoretic properties needed to be a certificate of hardness. This verification is only singly exponential (by essentially standard algorithms invariant theory). – Joshua Grochow Sep 19 '10 at 20:31
• Note that Mulmuley does not conjecture anything "positive" about the complexity of finding minimum circuits for SAT (if SAT circuits can be found in polynomial time, then surely $NP \subseteq P/poly$, the opposite of what he wants to show). Mulmuley's conjectures are about what he calls "explicit proofs" or "obstructions", the existence of which establishes lower bounds. It is those objects that Mulmuley believes can be found quickly. (I'm sure Joshua knows all this, I am just stating this for clarity.) – Ryan Williams Sep 19 '10 at 21:54
• @Ryan: Excellent point of clarification. It led me to wonder about this question: cstheory.stackexchange.com/questions/1514/… – Joshua Grochow Sep 20 '10 at 17:26

The definitions of "polynomial time" and "exponential time" describe the limiting behavior of the running time as the input size grows to infinity. On the other hand, any physical experiment necessarily considers only inputs of bounded size. Thus, there is absolutely no way to determine experimentally whether a given algorithm runs in polynomial time, exponential time, or something else.

Or in other words: what Robin said.

• Suppose several experiments are done that somehow encode NP-complete problems into real problems and let the nature solve them. And suppose that in all those experiments, it is discovered that there is a sufficiently large input size for which nature takes a lot of time in solving the problem, then will that be evidence in favor of the statement that nature cannot solve NP-complete problems efficiently? – Vinayak Pathak Sep 18 '10 at 15:31
• Absolutely not. Even if you could convince Nature to solve the problems optimally (unlike soap bubbles for Steiner trees, for example), and even if you could distinguish asymptotic behavior from a finite experiment, it might still be the case that Nature uses an inefficient algorithm. – Jeffε Sep 18 '10 at 16:50
• (From a philosophical standpoint, I simply don't see any difference between "convince nature to solve the problem" and "implement and run an algorithm to solve the problem". On the one hand, "a reliable technique to make a physical system solve a problem" is a workable definition of algorithm; on the other hand, humans and computers are both part of nature.) – Jeffε Sep 18 '10 at 16:59

Let me start out by saying that I agree completely with Robin. As regards the protein folding, there is a small issue. As with all such systems, protein folding can get stuck in local minima, which is something you seem to be neglecting. The more general problem is simply finding the ground state of some Hamiltonian. Actually, even if we consider only spins (i.e. qubits) this problem is complete for QMA.

Natural Hamiltonians are a little softer, however, than some of the artificial ones used to prove QMA completeness (which tend not to mirror natural interactions), but even when we restrict to natural two-body interactions on simple systems the result is still an NP-complete problem. Indeed, this forms the basis of an approach attempted to tackling NP problems using adiabatic quantum computing. Unfortunately it appears that this approach will not work for NP-complete problems, due to a rather technical issue to do with the energy level structure. This does however lead to an interesting consequence of there existing problems within NP which are not efficiently solvable by nature (by which I mean physical processes). It means that there exist systems which cannot cool efficiently. That is to say, it seems you can construct a physical system which takes exponentially long in the size of the system to come into thermal equilibrium with the environment.

• Correct me if I'm wrong, Do you imply that the NP Hardness Assumption must have physically observable consequences? – Mohammad Al-Turkistany Sep 19 '10 at 0:19
• I'm saying that if BQP does not contain NP (which certainly seems to be the case) then NP being hard certainly does have physical consequences. For very noisy systems it would seem like we could get rid of the BQP stage and get the result directly from NP being hard, but this requires some physical assumptions. – Joe Fitzsimons Sep 19 '10 at 0:44
• To clarify, I am saying that there are physical consequences to $P \neq NP$, which may also be true if $P=NP$. – Joe Fitzsimons Sep 19 '10 at 1:09

The study of real-world situations from a computational perspective is quite hard due to the continuous-discrete "jump". While all events in the real world (supposedly) are run in continuous time, the models we usually use are implemented in discrete time. Therefore, it is very tricky to define how small or large a step should be, what should be the size of the problem, etc.

I have written a summary on an Aaronson's paper on the subject, however it is not in English. See the original paper.

Personally, I have heard of another example of a real world problem modeled into computation. The paper is about control-systems models based on bird flocking.It turns out although it takes a short time in real life for birds, it's intractable ("a tower of 2s") when analyzed as a computational problem. See the paper by Bernard Chazelle for details.

[Edit: Clarified the part about the Chazelle paper. Thanks for providing precise information.]

• not just exponential. it's a tower of 2s actually. – Suresh Venkat Sep 18 '10 at 5:49
• Suresh is, of course, correct. Beyond that, the Chazelle paper is not an analysis of bird flocking: it's an analysis of well-known control-systems models based on bird flocking. In particular, his analysis requires use of a "hysteresis rule" that birds are not observed to obey themselves. See Chazelle's comment #3 here for more about this research program. – Aaron Sterling Sep 18 '10 at 14:43

I still vote for the n-body problem as an example of NP intractability. The gentlemen who refer to numeric solutions forget that the numeric solution is a recursive model, and not a solution in principle in the same way that an analytic solution is. Qui Dong Wang's analytic solution is intractable. Proteins which can fold, and planets which can orbit in systems of more than two bodies are physical systems, not algorithmic solutions of the kind which the P-NP problem addresses.

I must also appreciate chazisop's difficulties with solutions in continuous time. If either time or space is continuous, potential state spaces become uncountable (aleph one).

• The exact/analog 3-body problem isn't just NP-hard; it's undecidable. On the other hand, true physical systems aren't truly analog; you've just replaced one mathematical abstraction with another one. – Jeffε Jul 31 '13 at 7:57

We can't efficiently solve the $n$-body problem, but those rocks-for-brains planets seem to manage just fine.

• That's not true. We can indeed efficiently solve the n-body problem, it is simply that there is not an analytic solution. Numerical methods work just fine. – Joe Fitzsimons Sep 18 '10 at 21:09
• Exactly. I've never seen a planet exhibit an analytical solution for the n-body problem either, so the comparison is unfair. – Robin Kothari Sep 19 '10 at 0:02