PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Very low Entry average rating: No information on entry rating
[parent] polynomial hierarchy is a hierarchy (Result)

The polynomial hierarchy is a hierarchy. Specifically: $$ \Sigma^p_i\cup\Pi^p_i\subseteq\Delta^p_{i+1}\subseteq\Sigma^p_{i+1}\cap\Pi^p_{i+1} $$

Proof

To see that $\Sigma^p_i\cup\Pi^p_i\subseteq\Delta^p_{i+1}=\mathcal{P}^{\Sigma^p_i}$ , observe that the machine which checks its input against its oracle and accepts or rejects when the oracle accepts or rejects (respectively) is easily in $\mathcal{P}$ , as is the machine which rejects or accepts when the oracle accepts or rejects (respectively). These easily emulate $\Sigma^p_i$ and $\Pi^p_i$ respectively.

Since $\mathcal{P}\subseteq\mathcal{NP}$ , it is clear that $\Delta^p_i\subseteq\Sigma^p_i$ . Since $\mathcal{P}^{\mathcal{C}}$ is closed under complementation for any complexity class $\mathcal{C}$ (the associated machines are deterministic and always halt, so the complementary machine just reverses which states are accepting), if $L\in\mathcal{P}^{\Sigma^p_i}\subseteq\Sigma^p_i$ then so is $\overline{L}$ , and therefore $L\in\Pi^p_i$ .

Unlike the arithmetical hierarchy, the polynomial hierarchy is not known to be proper. Indeed, if $\mathcal{P}=\mathcal{NP}$ then $\mathcal{P}=\mathcal{PH}$ , so a proof that the hierarchy is proper would be quite significant.




"polynomial hierarchy is a hierarchy" is owned by uzeromay. [ full author list (2) | owner history (1) ]
(view preamble | get metadata)

View style:


This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: proof, polynomial hierarchy, arithmetical hierarchy, states, complementary, deterministic, complexity class, closed under, clear, oracle, machine

This is version 2 of polynomial hierarchy is a hierarchy, born on 2002-09-06, modified 2004-03-27.
Object id is 3438, canonical name is PolynomialHierarchyIsAHierarchy.
Accessed 2527 times total.

Classification:
AMS MSC68Q15 (Computer science :: Theory of computing :: Complexity classes )

Pending Errata and Addenda
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)