<p>Lipton <a href="http://rjlipton.wordpress.com/2013/11/26/theorems-from-physics/#comments">asks</a> for a physical proof of $P\neq NP$. </p>

<p>Can we even ask for a physical proof for understanding $P=BPP$ or $P\neq BPP$? Is there anything in physics that lets us avoid randomness? </p>

<p>Statistical mechanics and hence entropy is founded on randomness. </p>

<p>Entropy, information and randomness are all related and in this case can physical principles show $P=BPP$ or $P\neq BPP$ let alone the harder $P$ versus $NP$?</p>

<p>(Harder is relative here.. the guess here is that $P=BPP$ and $P\neq NP$ and showing classes that are hypothetically closer to be equal may be easier than showing classes that are hypothetically far-off to be separate).</p>

CC BY-SA 3.0
2013-11-26T22:39:39.377Z
there are indeed deep links between statistical mechanics and P vs NP in the form of the transition point of the satisfiability problem... yes, the connections between "what is physically possible" and "what is mathematically proven" reaches a close connection in the study of [thermodynamics](http://en.wikipedia.org/wiki/Thermodynamics) in general....
vzn
CC BY-SA 3.0
2013-11-26T22:46:19.143Z
There are not known to suffice separating the classes.
Turbo
<cc.complexity-theory><complexity-classes><it.information-theory><randomness><derandomization>
Physical Proof for P versus BPP
Turbo
# Physical Proof for P versus BPP

(Asked by: username_0 on 2013-11-26)

Lipton [asks](http://rjlipton.wordpress.com/2013/11/26/theorems-from-physics/#comments) for a physical proof of $P\neq NP$.

Can we even ask for a physical proof for understanding $P=BPP$ or $P\neq BPP$? Is there anything in physics that lets us avoid randomness?

Statistical mechanics and hence entropy is founded on randomness.

Entropy, information and randomness are all related and in this case can physical principles show $P=BPP$ or $P\neq BPP$ let alone the harder $P$ versus $NP$?

(Harder is relative here.. the guess here is that $P=BPP$ and $P\neq NP$ and showing classes that are hypothetically closer to be equal may be easier than showing classes that are hypothetically far-off to be separate).

**Tags:** cc.complexity-theory, complexity-classes, it.information-theory, randomness, derandomization
> **Comments:**
> **username_1**: there are indeed deep links between statistical mechanics and P vs NP in the form of the transition point of the satisfiability problem... yes, the connections between "what is physically possible" and "what is mathematically proven" reaches a close connection in the study of [thermodynamics](http://en.wikipedia.org/wiki/Thermodynamics) in general....  
> **username_0**: There are not known to suffice separating the classes.  

---

## 0 answers

