polynomial hierarchy is a hierarchy
The polynomial hierarchy is a hierarchy. Specifically:
To see that , 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 , as is the machine which rejects or accepts when the oracle accepts or rejects (respectively). These easily emulate and respectively.
Since , it is clear that . Since is closed under complementation for any complexity class (the associated machines are deterministic and always halt, so the complementary machine just reverses which states are accepting), if then so is , and therefore .
Unlike the arithmetical hierarchy, the polynomial hierarchy is not known to be proper. Indeed, if then , so a proof that the hierarchy is proper would be quite significant.
|Title||polynomial hierarchy is a hierarchy|
|Date of creation||2013-03-22 13:02:14|
|Last modified on||2013-03-22 13:02:14|
|Last modified by||uzeromay (4983)|