<p>I can see three related ways to understand the question: </p>

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

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

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

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

CC BY-SA 3.0
2013-01-28T01:32:09.270Z
2013-01-28T01:32:09.270Z
Gil Kalai
<p>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)</p>

CC BY-SA 3.0
2013-01-27T19:35:16.347Z
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?
vb le
CC BY-SA 3.0
2013-01-27T19:11:57.310Z
2013-01-27T19:11:57.310Z
Suresh Venkat
<p>To answer your original question:</p>

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

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

<p>He gave a nice talk at the University of Waterloo titled <a href="http://www.scottaaronson.com/talks/colloq2.ppt">Computational Intractability As A Law of Physics</a>
<a href="http://www.scottaaronson.com/talks/colloq2.ppt"></a></p>

CC BY-SA 3.0
2013-01-30T16:11:37.767Z
This is different from the P$\neq$NP conjecture, although it does imply it.
Peter Shor 
CC BY-SA 3.0
2014-04-02T16:18:49.357Z
+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.
labotsirc
CC BY-SA 3.0
2015-12-17T06:01:36.980Z
@labotsirc could you give your reasons?
Turbo
CC BY-SA 3.0
2013-01-30T16:04:55.597Z
2013-01-30T16:04:55.597Z
Mohammad Al-Turkistany
<p>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.</p>

CC BY-SA 3.0
2013-12-19T22:22:34.127Z
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.
Kaveh
CC BY-SA 3.0
2013-12-21T14:57:09.820Z
@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$.
Turbo
CC BY-SA 3.0
2013-12-19T22:18:48.733Z
2013-12-21T14:58:31.123Z
2013-12-21T14:58:31.123Z
Turbo
<p>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. </p>

CC BY-SA 3.0
2013-12-23T18:17:15.910Z
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.
Kyle Jones
CC BY-SA 3.0
2013-12-24T05:16:31.523Z
@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?
Thinniyam Srinivasan Ramanatha
CC BY-SA 3.0
2013-12-24T05:28:06.833Z
I meant that if a mathematical proof of the statement is produced, no evidence from the physical world can disprove it.
Thinniyam Srinivasan Ramanatha
CC BY-SA 3.0
2013-12-23T03:31:34.793Z
2013-12-23T03:31:34.793Z
Thinniyam Srinivasan Ramanatha
<p>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</p>

<p>Of course, Newton "is not right", and Einstein came after him.</p>

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

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

CC BY-SA 3.0
2013-01-28T17:06:44.100Z
Actually, there are still lots of candidates for NP-intermediate problems, whose exact complexity remains unresolved: http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc
Joshua Grochow
CC BY-SA 3.0
2013-01-28T20:37:17.637Z
this list is good to know, thanks for this comment !
Xoff
CC BY-SA 3.0
2013-01-28T14:06:19.850Z
2013-01-28T14:06:19.850Z
Xoff
<p>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</p>

<blockquote>
  <p>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.</p>
</blockquote>

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

<blockquote>
  <p>"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."</p>
</blockquote>

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

<p>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): </p>

<blockquote>
  <p>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... </p>
</blockquote>

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

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

CC BY-SA 3.0
2013-01-29T00:28:25.993Z
"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....
vzn
CC BY-SA 3.0
2013-01-29T15:34:54.957Z
@vzn: this is why mathematicians who said things like this were so annoying.
Peter Shor 
CC BY-SA 3.0
2013-01-29T17:23:57.640Z
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](http://en.wikipedia.org/wiki/Fields_Medal)] [writeup of razborovs monotone circuit lower bounds proof](http://gowers.files.wordpress.com/2009/05/razborov2.pdf). and of course the riemann conjecture is another Clay math problem.... along with other mostly math ones...
vzn
CC BY-SA 3.0
2013-01-27T23:35:01.917Z
2013-01-29T17:54:07.070Z
2013-01-29T17:54:07.070Z
Peter Shor 
<p>Many experts believe that the <span class="math-container">$\mathsf{P} \neq \mathsf{NP}$</span> conjecture is true and use it in their results. My concern is that the complexity strongly depends on the <span class="math-container">$\mathsf{P} \neq \mathsf{NP}$</span> conjecture.</p>
<p>So my question is:</p>
<blockquote>
<p>As long as the <span class="math-container">$\mathsf{P}\neq\mathsf{NP}$</span> 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 <a href="http://www.claymath.org/millenium-problems/p-vs-np-problem" rel="noreferrer">mathematical conjecture</a>
that maybe proved or disproved someday?</p>
</blockquote>
<p>Quote:</p>
<blockquote>
<p>&quot;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.&quot;</p>
<p>[Volker Strassen's <a href="http://ada00.math.uni-bielefeld.de/ICM/ICM1986.1/Main/icm1986.1.0016.0022.ocr.pdf" rel="noreferrer">laudation</a>
to the Nevanlinna Prize winner, Leslie G. Valian, in 1986]</p>
</blockquote>
<p>I ask this question when reading the post <a href="https://cstheory.stackexchange.com/questions/2074/physics-results-in-tcs">Physics results in TCS?</a>.
It is perhaps interesting to note that computational complexity has some similarities to (theoretical) physic: <strong>many important complexity results
have been proved by assuming <span class="math-container">$\mathsf{P} \neq \mathsf{NP}$</span>, while in theoretical physic results are proven by assuming some physical laws</strong>.
In this sense, <span class="math-container">$\mathsf{P} \neq \mathsf{NP}$</span> can be considered something like <span class="math-container">$E = mc^2$</span>.
Back to <a href="https://cstheory.stackexchange.com/questions/2074/physics-results-in-tcs">Physics results in TCS?</a>:</p>
<blockquote>
<p>Could (part of) TCS be a branch of natural sciences?</p>
</blockquote>
<h3>Clarification:</h3>
<p>(c.f. Suresh's answer below)</p>
<blockquote>
<p>Is it legitimate to say that the <span class="math-container">$\mathsf{P}\neq\mathsf{NP}$</span> conjecture in complexity theory is as fundamental as a physical laws in theoretical physics (as Strassen said)?</p>
</blockquote>

CC BY-SA 3.0
2013-01-27T20:38:55.517Z
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](http://cstheory.stackexchange.com/faq#dontask).
Tsuyoshi Ito
CC BY-SA 3.0
2013-01-27T20:48:01.727Z
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 ...
vb le
CC BY-SA 3.0
2013-01-27T21:52:06.033Z
After careful checking “What kind of questions should I not ask here?” (and other items) in FAQ, I still find that my question fits nicely here (among other soft-questions); I am very sorry for having different opinion. However, I have to accept your decision, of course.
vb le
CC BY-SA 3.0
2013-01-27T22:23:49.710Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2013-01-28T01:35:13.183Z
I think that this question is quite important and that in this case  we can make an exception for the tendency to avoid discussions.
Gil Kalai
CC BY-SA 3.0
2013-01-28T03:46:21.147Z
aaronson has recently been emphasizing that $P\neq NP$ is almost like a physical law or that in another less rigorous field of science such as physics, it would be assumed almost as a law. but everyone in complexity theory must surely agree that it is unequivocally a mathematical conjecture, but one which has realworld implications/consequences. therefore it has notably similarity to mathematical statements and theorems in physics and eg thermodynamics, where theorems actually refer to laws of the universe...
vzn
CC BY-SA 3.0
2013-01-28T14:16:36.893Z
I meant to leave this as a comment but I do not have the reputation to do so. This question is really interesting. I did not know about Strassen's point of view previuosly; thanks for the pointer! It would be nice for the complexity community/TCS if every one can understand the P vs NP mystery (with its importance and expert opinions) such as it is the case of the Fermat's Last Theorem. Especially, "our" P vs NP question is much more important than the FLT (mathematicians may forgive me). I do think that people working in complexity should find the ways to make P vs NP more popular for the gen
In Theory
CC BY-SA 3.0
2013-01-28T20:00:36.137Z
@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.
Tsuyoshi Ito
CC BY-SA 3.0
2013-01-28T21:27:19.967Z
@Gil, I share your view that this is important, but I agree with Tsuyoshi that it is probably better to happen on place more suitable for discussion. One thing we can do is to edit the question to make it constructive, for example asking what did Strassen meant by this statement would make it specific enough and Peter's post is an answer to it, or we can make it a reference request for information on the issue of regarding widely believed mathematical conjectures like $\mathsf{P}\neq\mathsf{NP}$ as physical laws, that would also make it an answerable question,
Kaveh
CC BY-SA 3.0
2013-01-28T21:28:34.257Z
where answers can refer to previous discussions about it in the mathematics/computer science literature, or discussions on the web including previous or future one on blogs (e.g. Scott's or yours in case you decide to post something about it on your blog). If we want to keep this open as it is I think it might be better to move the discussion about it to [meta].
Kaveh
CC BY-SA 3.0
2013-01-29T17:32:43.177Z
a related question.. what exactly did strassen mean that wrt P$\neq$NP conjecture, "the consequences of their failure are _so grotesque_...."   what exactly is "grotesque" about P=NP? is that the idea? at least one elite complexity theorist Lipton says its conceivable. exactly the opposite case could be made, that it would be revolutionary & lead to massively widespread efficient algorithms... is it "grotesque" because cryptography would fail? (impagliazzos worlds, etc)
vzn
CC BY-SA 3.0
2013-01-29T21:23:50.350Z
I did some rewording trying to make the post more focused based on your comments, feel free to roll back my edit or edit further.
Kaveh
CC BY-SA 3.0
2013-02-11T20:10:30.560Z
@Kaveh Thank you. The edits were appropriate.
vb le
CC BY-SA 3.0
2013-12-23T04:59:30.040Z
A physical law is only as good as the observations it is based upon , remember how there was a force called gravity, which was later on proved to be just a manifestation of the curvature of spacetime.
ARi
CC BY-SA 4.0
2021-03-30T18:01:47.943Z
@ARi “was proved to be”, ORLY? The statement relies on long obsolete (even in 2013) philosophies of science.
Incnis Mrsi
<cc.complexity-theory><soft-question><big-picture><p-vs-np><physics>
Should we consider $\mathsf{P} \neq \mathsf{NP}$ a law of nature?
vb le
# Should we consider $\mathsf{P} \neq \mathsf{NP}$ a law of nature?

(Asked by: username_0 on 2013-01-27)

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](http://www.claymath.org/millenium-problems/p-vs-np-problem)
> 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](http://ada00.math.uni-bielefeld.de/ICM/ICM1986.1/Main/icm1986.1.0016.0022.ocr.pdf)
> to the Nevanlinna Prize winner, Leslie G. Valian, in 1986]

I ask this question when reading the post [Physics results in TCS?](https://cstheory.stackexchange.com/questions/2074/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?](https://cstheory.stackexchange.com/questions/2074/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)?

**Tags:** cc.complexity-theory, soft-question, big-picture, p-vs-np, physics

> **Comments:**
> **username_1**: 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](http://cstheory.stackexchange.com/faq#dontask).  
> **username_0**: 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 ...  
> **username_0**: After careful checking “What kind of questions should I not ask here?” (and other items) in FAQ, I still find that my question fits nicely here (among other soft-questions); I am very sorry for having different opinion. However, I have to accept your decision, of course.  
> **username_1**: 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.  
> **username_2**: I think that this question is quite important and that in this case  we can make an exception for the tendency to avoid discussions.  
> **username_3**: aaronson has recently been emphasizing that $P\neq NP$ is almost like a physical law or that in another less rigorous field of science such as physics, it would be assumed almost as a law. but everyone in complexity theory must surely agree that it is unequivocally a mathematical conjecture, but one which has realworld implications/consequences. therefore it has notably similarity to mathematical statements and theorems in physics and eg thermodynamics, where theorems actually refer to laws of the universe...  
> **username_4**: I meant to leave this as a comment but I do not have the reputation to do so. This question is really interesting. I did not know about Strassen's point of view previuosly; thanks for the pointer! It would be nice for the complexity community/TCS if every one can understand the P vs NP mystery (with its importance and expert opinions) such as it is the case of the Fermat's Last Theorem. Especially, "our" P vs NP question is much more important than the FLT (mathematicians may forgive me). I do think that people working in complexity should find the ways to make P vs NP more popular for the gen  
> **username_1**: @username_2: 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.  
> **username_5**: @Gil, I share your view that this is important, but I agree with Tsuyoshi that it is probably better to happen on place more suitable for discussion. One thing we can do is to edit the question to make it constructive, for example asking what did Strassen meant by this statement would make it specific enough and Peter's post is an answer to it, or we can make it a reference request for information on the issue of regarding widely believed mathematical conjectures like $\mathsf{P}\neq\mathsf{NP}$ as physical laws, that would also make it an answerable question,  
> **username_5**: where answers can refer to previous discussions about it in the mathematics/computer science literature, or discussions on the web including previous or future one on blogs (e.g. Scott's or yours in case you decide to post something about it on your blog). If we want to keep this open as it is I think it might be better to move the discussion about it to [meta].  
> **username_3**: a related question.. what exactly did strassen mean that wrt P$\neq$NP conjecture, "the consequences of their failure are _so grotesque_...."   what exactly is "grotesque" about P=NP? is that the idea? at least one elite complexity theorist Lipton says its conceivable. exactly the opposite case could be made, that it would be revolutionary & lead to massively widespread efficient algorithms... is it "grotesque" because cryptography would fail? (impagliazzos worlds, etc)  
> **username_5**: I did some rewording trying to make the post more focused based on your comments, feel free to roll back my edit or edit further.  
> **username_0**: @username_5 Thank you. The edits were appropriate.  
> **username_6**: A physical law is only as good as the observations it is based upon , remember how there was a force called gravity, which was later on proved to be just a manifestation of the curvature of spacetime.  
> **username_7**: @username_6 “was proved to be”, ORLY? The statement relies on long obsolete (even in 2013) philosophies of science.  

---

## 7 answers

### Answer by username_10 on 2013-01-27. Score: 60 | Accepted answer

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

> **Comments:**
> **username_3**: "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....  
> **username_10**: @username_3: this is why mathematicians who said things like this were so annoying.  
> **username_3**: 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](http://en.wikipedia.org/wiki/Fields_Medal)] [writeup of razborovs monotone circuit lower bounds proof](http://gowers.files.wordpress.com/2009/05/razborov2.pdf). and of course the riemann conjecture is another Clay math problem.... along with other mostly math ones...  

---

### Answer by username_2 on 2013-01-28. Score: 21

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 by username_8 on 2013-01-27. Score: 16

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)

> **Comments:**
> **username_0**: 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?  

---

### Answer by username_9 on 2013-01-30. Score: 9

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](http://www.scottaaronson.com/talks/colloq2.ppt)

> **Comments:**
> **username_10**: This is different from the P$\neq$NP conjecture, although it does imply it.  
> **username_11**: +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.  
> **username_12**: @username_11 could you give your reasons?  

---

### Answer by username_12 on 2013-12-19. Score: 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.

> **Comments:**
> **username_5**: 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.  
> **username_12**: @username_5 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$.  

---

### Answer by username_13 on 2013-12-23. Score: 1

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.

> **Comments:**
> **username_14**: 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.  
> **username_13**: @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?  
> **username_13**: I meant that if a mathematical proof of the statement is produced, no evidence from the physical world can disprove it.  

---

### Answer by username_15 on 2013-01-28. Score: -3

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.

> **Comments:**
> **username_16**: Actually, there are still lots of candidates for NP-intermediate problems, whose exact complexity remains unresolved: http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc  
> **username_15**: this list is good to know, thanks for this comment !  

---

