Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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$. – Pål GD Feb 17 '13 at 21:24
I forgot the conclusion. Hence PH $ \subseteq \Sigma^p_k$. – Pål GD Feb 17 '13 at 21:30
@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? – Reza Feb 17 '13 at 22:18

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.