Should we consider $\mathsf{P} \neq \mathsf{NP}$ a law of nature?

Question

Many experts believe that the $\mathsf{P} \neq \mathsf{NP}$ conjecture is true and use it in their results. My concern is that the complexity strongly depends on the $\mathsf{P} \neq \mathsf{NP}$ conjecture.

So my question is:

As long as the $\mathsf{P}\neq\mathsf{NP}$ conjecture is not proven, can/should one consider it as a law of nature, as indicated in the quote from Strassen? Or should we treat it as a mathematical conjecture that maybe proved or disproved someday?

Quote:

"The evidence in favor of Cook's and Valiant's hypotheses is so overwhelming, and the consequences of their failure are so grotesque, that their status may perhaps be compared to that of physical laws rather than that of ordinary mathematical conjectures."

[Volker Strassen's laudation to the Nevanlinna Prize winner, Leslie G. Valian, in 1986]

I ask this question when reading the post Physics results in TCS?. It is perhaps interesting to note that computational complexity has some similarities to (theoretical) physic: many important complexity results have been proved by assuming $\mathsf{P} \neq \mathsf{NP}$, while in theoretical physic results are proven by assuming some physical laws. In this sense, $\mathsf{P} \neq \mathsf{NP}$ can be considered something like $E = mc^2$. Back to Physics results in TCS?:

Could (part of) TCS be a branch of natural sciences?

Clarification:

(c.f. Suresh's answer below)

Is it legitimate to say that the $\mathsf{P}\neq\mathsf{NP}$ conjecture in complexity theory is as fundamental as a physical laws in theoretical physics (as Strassen said)?

Answer 1

Strassen's statement needs to be put into context. This was an address to an audience of mathematicians in 1986, a time when many mathematicians did not have a high opinion of theoretical computer science. The complete statement is

For some of you it may seem that the theories discussed here rest on weak foundations. They do not. The evidence in favor of Cook's and Valiant's hypotheses is so overwhelming, and the consequences of their failure is so grotesque, that their status may perhaps be compared to that of physical laws rather than that of ordinary mathematical conjectures.

I am sure that Strassen had had conversations with pure mathematicians who said something along the lines of

"You're basing the whole of complexity theory on a house of cards. What if P=NP? Then all your theorems will be meaningless. Why don't you just put forth a little effort and prove that P$\neq$NP, rather than keep building a theory on such weak foundations."

In 2013, when P$\neq$NP has been a Clay prize problem for a dozen years, it may seem difficult to believe that any mathematicians actually had such attitudes; however, I can personally vouch that some did.

Strassen continues by saying that we should not give up looking for a proof of P$\neq$NP (thus indirectly implying that it is indeed a mathematical conjecture):

Nevertheless, a traditional proof would be of great interest, and it seems to me that Valiant's hypothesis may be easier to confirm than Cook's...

so maybe I would label it as a "working hypothesis" rather than a "physical law".

Let me finally note that mathematicians also use such working hypotheses. There are a large number of mathematics papers proving theorems whose statements run "Assuming the Riemann hypothesis is true, then ...".

Answer 2

I can see three related ways to understand the question:

1) Can we we regard $NP \ne P$ as a fundamental principle of computational complexity theory, even before we can prove it?

2) Does the $NP \ne P$ principle extends beyond its narrow mathematical meaning?

3) Does the $NP \ne P$ principle can be regarded as a physical law.

I think that there are good reasons to answer 'yes' or 'qualified yes' for all these three questions.

Answer 3

I'm not sure I understand. A physical law (of the kind you indicate) is a mathematical expression of a model (in that example, relativity) that claims to capture reality. A physical law can be proved wrong if the underlying mathematics is incorrect, but it can also be wrong if the underlying model changes (for example, newtonian mechanics). P vs NP is a specific mathematical conjecture that is true or false (and might be provably or not)

Answer 4

To answer your original question:

Yes at least Scott Aaronson believes that $P \ne NP$ is a law of nature. He proposed the following formulation

"The NP Hardness Assumption: There is no physical means to solve NP complete problems in polynomial time".

He gave a nice talk at the University of Waterloo titled Computational Intractability As A Law of Physics

Answer 5

First of all is the known weaker result $NL\neq PSPACE$ or the stronger conjecture $NP\neq coNP$ possible laws of nature? Then we can ask questions about if $P\neq NP$ is a law of nature.

Answer 6

The statement P≠NP can encoded as a statement $\phi$ about natural numbers. Since $\phi$ is either true or false about the naturals, the answer to the question is a purely mathematical one. This is definitely not a physical law which is subject to the nature of the physical world that we live in.

Answer 7

You can do a lots of experiments on speeds and velocities, and you will obtain overwhelming evidence to validate Newton's laws. Of course, you will see some very strange things in very particular experiments, like the speed of light in moving water, or some astronomical events. But your overwhelming pieces of evidence will say to you : Newton is right and those laws are what you need

Of course, Newton "is not right", and Einstein came after him.

For P=NP, we can see a lots of example where it seems P≠NP. But in some particular cases, we have strange things. If P≠NP, there are an infinite number of classes between them, so we should find some problems in NP that are not in P, but are not NP-complete. We don't know any of them, and most candidates were proven to be in P.

What you think about this problem depends on where you want to look at. I would not be surprised if P=NP.