Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 2 down vote favorite

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

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.