30
$\begingroup$

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

$\endgroup$
  • 10
    $\begingroup$ The website cstheory.stackexchange.com is not a suitable place for discussions. Please check “What kind of questions should I not ask here?” in FAQ. $\endgroup$ – Tsuyoshi Ito Jan 27 '13 at 20:38
  • 11
    $\begingroup$ Well, I hope someone could have a right answer for my question. I find Strassen's point of view is quite interesting, and, funnily enough, we did'nt talk about that. I will check FAQ now ... $\endgroup$ – vb le Jan 27 '13 at 20:48
  • 8
    $\begingroup$ You are asking for people’s opinion, not facts, so this question is clearly unsuitable in my opinion. You do not have to agree, but I hope that my stance about this is clear. $\endgroup$ – Tsuyoshi Ito Jan 27 '13 at 22:23
  • 30
    $\begingroup$ I think that this question is quite important and that in this case we can make an exception for the tendency to avoid discussions. $\endgroup$ – Gil Kalai Jan 28 '13 at 1:35
  • 3
    $\begingroup$ @Gil Kalai: There are many important things to discuss in this world, but cstheory.stackexchange.com is not the right place for them. Please discuss them somewhere else. $\endgroup$ – Tsuyoshi Ito Jan 28 '13 at 20:00
57
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ "why dont you just put forth a little effort and prove that P$\neq$NP..." — but probably massive effort has been put fwd ever since the beginning of the conjecture.... $\endgroup$ – vzn Jan 29 '13 at 0:28
  • 7
    $\begingroup$ @vzn: this is why mathematicians who said things like this were so annoying. $\endgroup$ – Peter Shor Jan 29 '13 at 15:34
  • $\begingroup$ ok, yeah, agreed that mathematicians, maybe somewhat unfairly, did not recognize P$\stackrel{?}{=}$NP as mathematically significant or possibly even fundamental until possibly decades after is inception & the Clay prize probably had a lot to do with helping that. an interesting near case study of this is gowers' [fields medalist] writeup of razborovs monotone circuit lower bounds proof. and of course the riemann conjecture is another Clay math problem.... along with other mostly math ones... $\endgroup$ – vzn Jan 29 '13 at 17:23
20
$\begingroup$

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.

$\endgroup$
12
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ I know that I overact with the quote of Strassen. My concern is that the complexity strongly depends on the P vs NP question, like physics on its laws (as you have clarified). So the question is: As long as the P vs. NP conjecture is not proven, can/should one consider it as a physical law, as indicated Strassen? $\endgroup$ – vb le Jan 27 '13 at 19:35
7
$\begingroup$

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

$\endgroup$
  • 13
    $\begingroup$ This is different from the P$\neq$NP conjecture, although it does imply it. $\endgroup$ – Peter Shor Jan 30 '13 at 16:11
  • 7
    $\begingroup$ +1. From one of the conversations i had with a friend , i ended up believeing that the universe would have no reason to exist if P = NP. $\endgroup$ – labotsirc Apr 2 '14 at 16:18
  • 2
    $\begingroup$ @labotsirc could you give your reasons? $\endgroup$ – T.... Dec 17 '15 at 6:01
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ From mathematical point your answer makes sense, but the question is not mathematical. I think P vs. NP is a more natural and intuitive question so it is not unreasonable to think that P vs. NP is more suitable as the starting point. At the core I think the issue is not mathematics but how the mathematical models of computation that we have built correspond to the real world and what can be done in it. $\endgroup$ – Kaveh Dec 19 '13 at 22:22
  • 1
    $\begingroup$ @Kaveh Why $NP\neq coNP$ is not more natural? To me this seems to be profoundly as important or even more important than $P\neq NP$. $\endgroup$ – T.... Dec 21 '13 at 14:57
1
$\begingroup$

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.

$\endgroup$
  • 8
    $\begingroup$ Except that we know that if physical laws didn't prevent Blum–Shub–Smale machines from being created in our universe, P and NP would be equivalent. So the question is related to the physical world in that sense. $\endgroup$ – Kyle Jones Dec 23 '13 at 18:17
  • $\begingroup$ @KyleJones Sorry, I don't understand what you are saying (probably because I don't know enough about BSS model). Could you give me a reference which explains this in more detail? $\endgroup$ – Thinniyam Srinivasan Ramanatha Dec 24 '13 at 5:16
  • $\begingroup$ I meant that if a mathematical proof of the statement is produced, no evidence from the physical world can disprove it. $\endgroup$ – Thinniyam Srinivasan Ramanatha Dec 24 '13 at 5:28
-4
$\begingroup$

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.

$\endgroup$
  • 7
    $\begingroup$ Actually, there are still lots of candidates for NP-intermediate problems, whose exact complexity remains unresolved: cstheory.stackexchange.com/questions/79/… $\endgroup$ – Joshua Grochow Jan 28 '13 at 17:06
  • $\begingroup$ this list is good to know, thanks for this comment ! $\endgroup$ – Xoff Jan 28 '13 at 20:37

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.