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

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

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

Answer 9

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

Answer 10

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