Polynomial Hierarchy - Definitions

Definitions

There are multiple equivalent definitions of the classes of the polynomial hierarchy.

  1. For the oracle definition of the polynomial hierarchy, define
    where P is the set of decision problems solvable in polynomial time. Then for i ≥ 0 define
    where AB is the set of decision problems solvable by a Turing machine in class A augmented by an oracle for some complete problem in class B. For example, and is the class of problems solvable in polynomial time with an oracle for some NP-complete problem.
  2. For the existential/universal definition of the polynomial hierarchy, let be a language (i.e. a decision problem, a subset of {0,1}*), let be a polynomial, and define
    where is some standard encoding of the pair of binary strings x and w as a single binary string. L represents a set of ordered pairs of strings, where the first string x is a member of, and the second string w is a "short" witness testifying that x is a member of . In other words, if and only if there exists a short witness w such that . Similarly, define
    Note that De Morgan's Laws hold: and, where Lc is the complement of L. Let be a class of languages. Extend these operators to work on whole classes of languages by the definition
    Again, De Morgan's Laws hold: and, where . The classes NP and co-NP can be defined as, and, where P is the class of all feasibly (polynomial-time) decidable languages. The polynomial hierarchy can be defined recursively as
    Note that, and . This definition reflects the close connection between the polynomial hierarchy and the arithmetical hierarchy, where R and RE play roles analogous to P and NP, respectively. The analytic hierarchy is also defined in a similar way to give a hierarchy of subsets of the real numbers.
  3. 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.

Read more about this topic:  Polynomial Hierarchy

Famous quotes containing the word definitions:

    “Lord Byron is an exceedingly interesting person, and as such is it not to be regretted that he is a slave to the vilest and most vulgar prejudices, and as mad as the winds?
    There have been many definitions of beauty in art. What is it? Beauty is what the untrained eyes consider abominable.”
    —Edmond De Goncourt (1822–1896)

    “What I do not like about our definitions of genius is that there is in them nothing of the day of judgment, nothing of resounding through eternity and nothing of the footsteps of the Almighty.”
    —G.C. (Georg Christoph)

    “The loosening, for some people, of rigid role definitions for men and women has shown that dads can be great at calming babies—if they take the time and make the effort to learn how. It’s that time and effort that not only teaches the dad how to calm the babies, but also turns him into a parent, just as the time and effort the mother puts into the babies turns her into a parent.”
    —Pamela Patrick Novotny (20th century)