Polynomial hierarchy Guide, Meaning , Facts, Information and Description

In computational complexity theory, the polynomial hierarchy is a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines.

Table of contents

1 Definitions 2 Relations between complexity classes 3 Problems in polynomial hierarchy 4 References

Definitions

Define

Then for i ≥ 0 define

Where A^B is the set of decision problems solvable by a Turing machine in class A augmented by an oracle for some problem in class B. For example, Σ₁P = NP, Π₁P = co-NP, and Δ₂P = P^NP is the class of problems solvable in polynomial time with an oracle for some problem in NP.

Relations between complexity classes

The definitions imply the relations:

It is an open question whether any of these containments are proper (most people expect that they all are). If any , then the hierarchy collapses to level k: for all , . In particular, if P = NP, then the hierarchy collapses completely.

An equivalent definition in terms of alternating Turing machines defines (respectively, ) as the set of decision problems solvable in polynomial time on an alternating Turing machine with alternations starting in an existential (respectively, universal) state.

The union of all classes in the polynomial hierarchy is the complexity class PH.

The polynomial hierarchy is an analogue (at much lower complexity) of the exponential hierarchy and arithmetical hierarchy.

It is known that PH is contained within PSPACE, but it is not known whether the two classes are equal.

If the polynomial hierarchy has any complete problems, then it has only finitely many distinct levels. Since PSPACE is known to contain PSPACE-complete problems, we know that if PSPACE = PH, then the polynomial hierarchy must collapse.

Problems in polynomial hierarchy

An example of a natural problem in Σ₂P is circuit minimization: given a circuit A computing a Boolean function f and a number k, determine if there is a circuit with at most k gates that computes the same function f. Let be the set of all boolean circuits. The language L = { : A and B are circuits, B has less than k gates, and } is decidable in polynomial time. The language CM = { : there exists a circuit B such that A and B compute the same function } is the circuit minimization language. is in because, given , if and only if there exists a circuit B such that for all inputs x, is in L, then is in CM, and because L is decidable in polynomial time.

A complete problem for Σ_kP is satisfiability for quantified Boolean formulas with k alternations of quantifiers (abbreviated QBF_k or QSAT_k). In this problem, we are given a Boolean formula f with variables partitioned into k sets X₁, ..., X_k. We have to determine if it is true that

That is, is there an assignment of values to variables in X₁ such that, for all assignements of values in X₂, there exists an assignement of values to variables in X₃, ... f is true?

The variant above is complete for Σ_kP. The variant in which the first quantifier is "for all", the second is "exists", etc., is complete for Π_kP.

References

1. L. Stockmeyer. The polynomial hierarchy. Theoretical Computer Science, vol.3, pp.1-22, 1976. The paper which introduced the polynomial hierarchy.
2. C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. Chapter 17. Polynomial hierarchy. A commonly used textbook

This is an Article on Polynomial hierarchy. Page Contains Information, Facts Details or Explanation Guide About Polynomial hierarchy

	Web www.E-paranoids.com