Polynomial hierarchy

From Academic Kids

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.

Contents

Definitions

There are two equivalent definitions of the classes of the polynomial hierarchy: the "oracle" characterization and the "existential/universal" characterization.

  1. For the oracle definition of the polynomial hierarchy, define
    <math>\Delta_0\rm{P} := \Sigma_0\mbox{P} := \Pi_0\mbox{P} := \mbox{P}<math>
    Then for i ≥ 0 define
    <math>\Delta_{i+1}\mbox{P} := \mbox{P}^{\Sigma_i\rm{P}}<math>
    <math>\Sigma_{i+1}\mbox{P} := \mbox{NP}^{\Sigma_i\rm{P}}<math>
    <math>\Pi_{i+1}\mbox{P} := \mbox{co-NP}^{\Sigma_i\rm{P}}<math>
    Where AB 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, Σ1P = NP, Π1P = co-NP, and Δ2P = PNP is the class of problems solvable in polynomial time with an oracle for some problem in NP.
  2. For the existential/universal definition of the polynomial hierarchy, let <math>L<math> be a language, let <math>p<math> be a polynomial, and define
    <math> \exists^p L := \left\{ x \in \{0,1\}^* \ \left| \ \left( \exists w \in \{0,1\}^{\leq p(|x|)} \right) \langle x,w \rangle \in L \right. \right\} <math>
    In other words, <math>L<math> represents a set of ordered pairs of strings, where the first string <math>x<math> is a member of <math>\exists^p L<math>, and the second string <math>w<math> is a "short" (<math> \leq p(|x|) <math>) witness testifying that <math>x<math> is a member of <math>\exists^p L<math>. In other words, <math>x \in \exists^p L<math> if and only if there exists a short witness <math>w<math> such that <math> \langle x,w \rangle \in L <math>. Similarly, define
    <math> \forall^p L := \left\{ x \in \{0,1\}^* \ \left| \ \left( \forall w \in \{0,1\}^{\leq p(|x|)} \right) \langle x,w \rangle \in L \right. \right\} <math>
    Note that deMorgan's Laws hold: <math> \left( \exists^p L \right)^c = \forall^p L^c <math> and <math> \left( \forall^p L \right)^c = \exists^p L^c <math>, where <math> L^c <math> is the complement of <math>L<math>. Let <math>\mathcal{C}<math> be a class of languages. Extend these operators to work on whole classes of languages by the definition
    <math>\exists^{\rm P} \mathcal{C} := \left\{ \exists^p L \ | \ p \mbox{ is a polynomial and } L \in \mathcal{C} \right\}<math>
    <math>\forall^{\rm P} \mathcal{C} := \left\{ \forall^p L \ | \ p \mbox{ is a polynomial and } L \in \mathcal{C} \right\}<math>
    Note that deMorgan's Laws hold: <math> {\rm co} \exists^{\rm P} \mathcal{C} = \forall^{\rm P} {\rm co} \mathcal{C} <math> and <math> {\rm co} \forall^{\rm P} \mathcal{C} = \exists^{\rm P} {\rm co} \mathcal{C} <math>, where <math>{\rm co}\mathcal{C} = \left\{ L^c | L \in \mathcal{C} \right\}<math>. The classes NP and co-NP can be defined as <math> {\rm NP} = \exists^{\rm P} {\rm P} <math>, and <math> {\rm coNP} = \forall^{\rm P} {\rm P} <math>, where P is the class of all feasibly (polynomial-time) decidable languages. The polynomial hierarchy can be define recursively as
    <math> \Sigma_0^{\rm P} := \Pi_0^{\rm P} := {\rm P} <math>
    <math> \Sigma_{k+1}^{\rm P} := \exists^{\rm P} \Pi_k^{\rm P} <math>
    <math> \Pi_{k+1}^{\rm P} := \forall^{\rm P} \Sigma_k^{\rm P} <math>
    Note that <math> {\rm NP} = \Sigma_1^{\rm P} <math>, and <math> {\rm coNP} = \Pi_1^{\rm P} <math>. This definition reflects the close connection between the polynomial hierarchy and the arithmetical hierarchy, where DEC (decidable languages) and CE (computably enumerable languages) play roles analogous to P and NP, respectively.

Relations between complexity classes

The definitions imply the relations:

<math>\Sigma_i\mbox{P} \subseteq \Delta_{i+1}\mbox{P} \subseteq \Sigma_{i+1}\mbox{P}<math>
<math>\Pi_i\mbox{P} \subseteq \Delta_{i+1}\mbox{P} \subseteq \Pi_{i+1}\mbox{P}<math>

It is an open question whether any of these containments are proper (most people expect that they all are). If any <math>\Sigma_k\rm{P} = \Sigma_{k+1}\rm{P}<math>, then the hierarchy collapses to level k: for all <math>i > k<math>, <math>\Sigma_i\rm{P} = \Sigma_k\rm{P}<math>. In particular, if P = NP, then the hierarchy collapses completely.

An equivalent definition in terms of alternating Turing machines defines <math>\Sigma_k\rm{P}<math> (respectively, <math>\Pi_k\rm{P}<math>) as the set of decision problems solvable in polynomial time on an alternating Turing machine with <math>k<math> 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. One useful reformulation of this problem is that PH = PSPACE if and only if second order logic gains no additional power from the addition of a transitive closure operator.

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 <math>\Sigma_2^P<math> 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 <math> \mathcal{C} <math> be the set of all boolean circuits. The language

    <math> L = \left\{ \langle A,k,B,x \rangle \in \mathcal{C} \times \mathbb{N} \times \mathcal{C} \times \{0,1\}^*
    \left| B \mbox{ has at most } k \mbox{ gates, and } A(x)=B(x) \right. \right\} <math> <p> is decidable in polynomial time. The language <p>
    <math> CM = \left\{ \langle A,k \rangle \in \mathcal{C} \times \mathbb{N}
    \left| \begin{matrix} \mbox{there exists a circuit } B \mbox{ with at most } k \mbox{ gates } \\ \mbox{ such that } A \mbox{ and } B \mbox{ compute the same function} \end{matrix} \right. \right\} <math> <p> is the circuit minimization language. <math> CM \in \Sigma_2^P (= \exists^{\rm P} \forall^{\rm P} {\rm P}) <math> because, given <math> \langle A,k \rangle <math>, if and only if there exists a circuit <math>B<math> with at most <math>k<math> gates, such that for all inputs <math>x<math>, <math> \langle A,k,B,x \rangle \in L <math>, then <math> \langle A,k \rangle \in CM<math>, and because <math>L<math> is decidable in polynomial time.
  • A complete problem for ΣkP is satisfiability for quantified Boolean formulas with k alternations of quantifiers (abbreviated QBFk or QSATk). In this problem, we are given a Boolean formula f with variables partitioned into k sets X1, ..., Xk. We have to determine if it is true that
    <math> \exists X_1 \forall X_2 \exists X_3 \ldots f<math>
    That is, is there an assignment of values to variables in X1 such that, for all assignements of values in X2, there exists an assignement of values to variables in X3, ... 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. </ul>

    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

Navigation

Academic Kids Menu

  • Art and Cultures
    • Art (http://www.academickids.com/encyclopedia/index.php/Art)
    • Architecture (http://www.academickids.com/encyclopedia/index.php/Architecture)
    • Cultures (http://www.academickids.com/encyclopedia/index.php/Cultures)
    • Music (http://www.academickids.com/encyclopedia/index.php/Music)
    • Musical Instruments (http://academickids.com/encyclopedia/index.php/List_of_musical_instruments)
  • Biographies (http://www.academickids.com/encyclopedia/index.php/Biographies)
  • Clipart (http://www.academickids.com/encyclopedia/index.php/Clipart)
  • Geography (http://www.academickids.com/encyclopedia/index.php/Geography)
    • Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
    • Maps (http://www.academickids.com/encyclopedia/index.php/Maps)
    • Flags (http://www.academickids.com/encyclopedia/index.php/Flags)
    • Continents (http://www.academickids.com/encyclopedia/index.php/Continents)
  • History (http://www.academickids.com/encyclopedia/index.php/History)
    • Ancient Civilizations (http://www.academickids.com/encyclopedia/index.php/Ancient_Civilizations)
    • Industrial Revolution (http://www.academickids.com/encyclopedia/index.php/Industrial_Revolution)
    • Middle Ages (http://www.academickids.com/encyclopedia/index.php/Middle_Ages)
    • Prehistory (http://www.academickids.com/encyclopedia/index.php/Prehistory)
    • Renaissance (http://www.academickids.com/encyclopedia/index.php/Renaissance)
    • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
    • United States (http://www.academickids.com/encyclopedia/index.php/United_States)
    • Wars (http://www.academickids.com/encyclopedia/index.php/Wars)
    • World History (http://www.academickids.com/encyclopedia/index.php/History_of_the_world)
  • Human Body (http://www.academickids.com/encyclopedia/index.php/Human_Body)
  • Mathematics (http://www.academickids.com/encyclopedia/index.php/Mathematics)
  • Reference (http://www.academickids.com/encyclopedia/index.php/Reference)
  • Science (http://www.academickids.com/encyclopedia/index.php/Science)
    • Animals (http://www.academickids.com/encyclopedia/index.php/Animals)
    • Aviation (http://www.academickids.com/encyclopedia/index.php/Aviation)
    • Dinosaurs (http://www.academickids.com/encyclopedia/index.php/Dinosaurs)
    • Earth (http://www.academickids.com/encyclopedia/index.php/Earth)
    • Inventions (http://www.academickids.com/encyclopedia/index.php/Inventions)
    • Physical Science (http://www.academickids.com/encyclopedia/index.php/Physical_Science)
    • Plants (http://www.academickids.com/encyclopedia/index.php/Plants)
    • Scientists (http://www.academickids.com/encyclopedia/index.php/Scientists)
  • Social Studies (http://www.academickids.com/encyclopedia/index.php/Social_Studies)
    • Anthropology (http://www.academickids.com/encyclopedia/index.php/Anthropology)
    • Economics (http://www.academickids.com/encyclopedia/index.php/Economics)
    • Government (http://www.academickids.com/encyclopedia/index.php/Government)
    • Religion (http://www.academickids.com/encyclopedia/index.php/Religion)
    • Holidays (http://www.academickids.com/encyclopedia/index.php/Holidays)
  • Space and Astronomy
    • Solar System (http://www.academickids.com/encyclopedia/index.php/Solar_System)
    • Planets (http://www.academickids.com/encyclopedia/index.php/Planets)
  • Sports (http://www.academickids.com/encyclopedia/index.php/Sports)
  • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
  • Weather (http://www.academickids.com/encyclopedia/index.php/Weather)
  • US States (http://www.academickids.com/encyclopedia/index.php/US_States)

Information

  • Home Page (http://academickids.com/encyclopedia/index.php)
  • Contact Us (http://www.academickids.com/encyclopedia/index.php/Contactus)

  • Clip Art (http://classroomclipart.com)
Toolbox
Personal tools