We know that at the end computation should be done by physical systems which follow laws of physics. I know there are some researches that study the phase transition phenomenon in physics and try to connect it with some properties in complexity theory (such as P and NP famous problem ). Just a quick review for example the phase transition happens from 2-SAT problem to 3-SAT problem. The first one is in P and the second one is NP-Complete.

My question is that: Is there any study that shows the mapping of Polynomial Hierarchy (PH) and multi-phase systems? Is there any mapping between PH-Complete problems and real physical system states? If so, are all levels of these hierarchy stable?

  • 2
    $\begingroup$ If there are PH-complete problems, then the polynomial hierarchy collapses. Proof: Consider a problem $P$ which is complete for PH. Since $P \in $ PH, it appears in some level $\Sigma^p_k$. Since any problem $Q \in $ PH reduces to $P$, it follows that $Q \in \Sigma^p_k$. $\endgroup$
    – Pål GD
    Feb 17, 2013 at 21:24
  • $\begingroup$ I forgot the conclusion. Hence PH $ \subseteq \Sigma^p_k$. $\endgroup$
    – Pål GD
    Feb 17, 2013 at 21:30
  • $\begingroup$ @PålGD: we know that If the polynomial hierarchy has any complete problems, then it has only finitely many distinct levels. considering this fact are there any similar analogies in physical systems? $\endgroup$
    – Reza
    Feb 17, 2013 at 22:18


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.