Polynomial Hierarchy - Problems in The Polynomial Hierarchy

Problems in The Polynomial Hierarchy

  • An example of a natural problem in is circuit minimization: given a number k and a circuit A computing a Boolean function f, 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 = \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\}
    is decidable in polynomial time. The language
    \mathit{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\}
    is the circuit minimization language. because is decidable in polynomial time and because, given, if and only if there exists a circuit such that for all inputs, .
  • A complete problem for is satisfiability for quantified Boolean formulas with k alternations of quantifiers (abbreviated QBFk or QSATk). This is the version of the boolean satisfiability problem for . 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
    That is, is there an assignment of values to variables in X1 such that, for all assignments of values in X2, there exists an assignment of values to variables in X3, ... f is true? The variant above is complete for . The variant in which the first quantifier is "for all", the second is "exists", etc., is complete for .

Read more about this topic:  Polynomial Hierarchy

Famous quotes containing the words problems in, problems and/or hierarchy:

    “I have a horror of people who speak about the beautiful. What is the beautiful? One must speak of problems in painting!”
    —Pablo Picasso (1881–1973)

    “Imagination is a valuable asset in business and she has a sister, Understanding, who also serves. Together they make a splendid team and business problems dissolve and the impossible is accomplished by their ministrations.... Imagination concerning the world’s wants and the individual’s needs should be the Alpha and Omega of self-education.”
    —Alice Foote MacDougall (1867–1945)

    “In a hierarchy every employee tends to rise to his level of incompetence.”
    —Laurence J. Peter (1919–1990)