Motivation
The polynomial hierarchy is defined by alternating polynomial-length quantifiers followed by an efficiently checkable predicate. To make a concrete complete problem, we would like that predicate to be a Boolean formula. A polynomial-time computation can be represented by a polynomial-size circuit, but blindly expanding a shared circuit into a formula may make it exponentially large. Introducing gate variables preserves the size; the subtle question is where to quantify them without creating an extra alternation.
The last quantifier determines the answer. With an existential final block, we ask for a consistent accepting gate assignment. With a universal final block, we require every consistent gate assignment to be accepting. Consistency determines a unique assignment, so both tests express the same circuit value.
Definitions
Definition 8.2.1
(Fixed-alternation quantified formulas)
Fix an integer . A -quantified Boolean formula is a well-formed expression
where is a Boolean formula and the blocks are pairwise disjoint lists of Boolean variables, alternating from an existential block. A block may be empty; it then has the single assignment given by the empty string. The corresponding problem starts with a universal block and alternates. The integer is fixed as part of the problem definition, not supplied as an unbounded input parameter. Invalid encodings are rejected deterministically.
The hierarchy classes and use the analogous fixed number of alternating polynomial-length string blocks followed by a polynomial-time predicate. A deterministic polynomial-time many-one reduction maps to one formula whose truth is equivalent to membership of .
We use the standard uniform circuit construction from the companion verifier-to-circuit unit: a fixed polynomial-time predicate and a length bound yield, in polynomial time, a polynomial-size Boolean circuit evaluating on all inputs of the specified lengths. The input can be hardwired into that circuit.
Theorem
Theorem 8.2.2
(Fixed-alternation formula completeness)
For every fixed , truth of -quantified Boolean formulas is -complete under deterministic polynomial-time many-one reductions. Truth of the corresponding formulas is -complete.
For the existential problem is ordinary formula satisfiability. For larger fixed this theorem gives a complete problem at that level. It does not show that two levels differ, and it is distinct from a formula problem with an unbounded number of alternating blocks.
Concept lensAlgorithmic
A quantified formula as a game
Read each block as a move in a game with rounds. The owner of block chooses its values after seeing the earlier blocks: the existential player owns the existential blocks, the universal player the universal ones. The formula is true exactly when the existential player has a strategy, with each choice allowed to depend on the earlier moves, that makes true against every play of the opponent. This is why order matters: in the choice of may depend on .
Proof
Proof
(Membership and hardness via gate variables)
Membership follows directly from the definition: quantify the block assignments in the displayed order and evaluate the formula in deterministic polynomial time. The total number of variables in any block is bounded by the input length. An empty block has one possible empty assignment, so it preserves truth for either quantifier.
For hardness, take any . There are a polynomial and a deterministic polynomial-time predicate such that
where each has length ; different polynomial bounds can be padded and ignored extra bits do not change a quantifier over a nonempty domain. For input , construct in polynomial time a circuit whose free inputs are the bits of all and whose output is . Give each internal gate a fresh variable; let be the list of these variables.
Construct a formula as the conjunction of local constraints saying that every gate variable equals its gate's operation on its input variables or input literals. Let denote the output value, using an input literal or constant directly if the output is not an internal gate. The formula has polynomial size because each bounded-fan-in gate contributes a constant-size local constraint. For every fixed there is exactly one assignment to satisfying : evaluate the gates in topological order. On that assignment .
If , add to the last existential block and use the matrix
If , add to the last universal block and use
Implication is a Boolean abbreviation and increases formula size only by a constant factor. For each fixed assignment to the original variables, the first matrix has a satisfying exactly when . The second is true for every exactly when : inconsistent make the implication true, and the one consistent assignment has the circuit output. Consequently this replacement preserves truth inside every outer quantifier and adds no new quantifier block. It also preserves polynomial output size and is computable in polynomial time.
The proof for is identical: use the corresponding outer quantifier pattern and choose the same consistency construction according to the type of its last block. This proves both completeness claims.
Proof X-ray
Why the last block decides the connective
The non-obvious move is where the gate variables go: they join the existing last block, so no alternation is added. This works because of two facts about the circuit. For each fixed there is exactly one assignment to satisfying , with existence and uniqueness both coming from evaluation in topological order, and on it . Both facts are used in each case. For , existence supplies the witness when , and uniqueness shows that no other assignment can certify acceptance. For , existence shows that the consistent assignment must accept, and uniqueness shows that no other consistent assignment can fail.
The connective must match the quantifier. Inconsistent assignments do not describe the circuit, so an existential block must be unable to use them (conjunction makes them false) and a universal block must be unable to be refuted by them (implication makes them true). Acyclicity is what lets the argument close: with a feedback loop, a consistent assignment might not exist or might not be unique.
Worked examples
Worked example 8.2.3
(Order of two quantifiers)
For one-bit variables, is true: choose . But is false: after either fixed choice of , the opposite value of makes equality false. In contrast, is true because the inner existential choice may depend on . Quantifier order changes the permitted dependence of choices.
Worked example 8.2.4
(Universal gate verification)
Suppose a circuit outputs and has a gate variable . Its consistency formula is . For , every satisfies : the inconsistent choice satisfies the implication vacuously, and the consistent satisfies the conclusion. For , the consistent choice makes the implication false. Thus universal verification returns the circuit's value, not the conjunction of all arbitrary gate values.
Matrix form depends on the final quantifier
Theorem 8.2.5
(CNF and DNF versions)
For each fixed alternating pattern, the truth problem remains complete for its hierarchy level when the matrix is required to be in conjunctive normal form (CNF) if its last block is existential, or disjunctive normal form (DNF) if its last block is universal. The same conclusion holds for either existential or universal initial block.
Proof
(Gate clauses give CNF and DNF)
Use a circuit with bounded-fan-in AND, OR and NOT gates. Each gate-consistency condition has a constant-size CNF. For example, if is the output of an AND gate on , the equivalence is expressed by
A NOT or OR gate has an analogous constant-size set of clauses. Consequently can be written as a polynomial-size conjunction of clauses. If the output is a constant or input wire rather than a gate, treat its assertion as the corresponding constant or one-literal formula.
When the last block is existential, is already CNF after adding the single output clause. When the last block is universal,
Each is a conjunction of the negated literals of one clause, and is a one-literal term. The result is a DNF of polynomial size. No distributive expansion over all combinations of clauses is performed. The previous proof establishes that these formulas preserve the quantified circuit value, so the same reductions prove hardness for the restricted matrices. Membership remains immediate.
Worked example 8.2.6
(Converting one AND gate)
For the gate , the CNF above has three clauses. Its negation, together with the asserted output, gives the DNF
For , this DNF is true for both values of . If , the consistent assignment makes every term false. Thus universally quantifying tests the gate's real output. The first three terms detect local inconsistency; the last asserts acceptance on the consistent assignment.
A warning about the opposite normal form
The final quantifier is not a cosmetic detail. Consider formulas of the form where is CNF. This restricted problem is in NP. Guess , substitute it into every clause, and test each remaining clause separately. A disjunction of universal literals is true under every assignment exactly when it contains a variable together with its negation, unless the existential part of the clause is already true. A non-tautological remaining clause can be falsified by setting each of its universal literals false. Universal quantification distributes over the conjunction of clauses, so this clause-by-clause test is sufficient.
The same problem is NP-hard: an ordinary CNF formula can be used as while the universal block contains a dummy variable that does not occur. It is therefore NP-complete. By contrast, the theorem supplies -completeness for an existential-universal prefix with a DNF matrix. These facts do not prove that differs from ; they show only that one normal-form restriction has a simpler verified upper bound.
Worked example 8.2.7
(A universal clause can fail on one assignment)
Consider . If , both clauses are true for every . If , neither remaining universal clause is a tautology, so each can be falsified by a choice of ; the conjunction certainly cannot hold for all choices. The formula is true exactly because the existential player can choose . By contrast, a clause is true for every regardless of .
Common mistakes
Two errors are the most common in this construction.
Counterexample mode
The same connective does not work in both blocks
It is tempting to use whatever the last quantifier is. For a universal last block this fails. Take the gate as the output and , so the circuit accepts. The assignment is inconsistent: is false. Then is false, because falsifies the conjunction, although the circuit accepts. The opposite error also occurs: with in an existential block and , the inconsistent choice makes the antecedent false, so is true although the circuit rejects. The correct pairing is conjunction for an existential last block and implication for a universal one.
Common mistake
(Adding a new gate block)
Adding an existential gate block after a final universal block creates a new alternation, so the circuit would no longer sit inside the given level. Saying that circuit evaluation is efficient does not justify the change. The gate variables must join the block that is already last.
Common mistake
(CNF after a universal last block)
The stated theorem allows any Boolean formula as the matrix. A restricted matrix needs its own reduction and must respect the last quantifier. For example, with in CNF lies in NP, as shown above, so it cannot be -complete unless .
Summary
Fixed alternating quantifier patterns have natural complete formula problems. A polynomial-size circuit becomes a polynomial-size formula with gate variables, and an existential conjunction or universal implication places those variables in the existing final block. This completeness result does not resolve any separation within the polynomial hierarchy.
Exercises
Quick check
(Decide the truth of for one-bit .)
Let depend on .
Solution · Answer
It is true: for each , choose .
Quick check
(Why is the gate-assignment consistency formula polynomial in circuit size?)
Count the constraints.
Solution · Answer
Each bounded-fan-in gate contributes a constant-size Boolean constraint; the conjunction contains one such constraint per gate and uses only polynomially many variable names.
Quick check
(If the last block is universal, explain why inconsistent gate assignments cannot falsify .)
Which assignment can falsify an implication?
Solution · Answer
An inconsistent assignment makes the antecedent false, so the implication is true independently of its conclusion. The unique consistent assignment is the only one that can falsify it.
Quick check
(What changes in the construction for a formula whose final block is existential?)
Which quantifier is last?
Solution · Answer
Add the gate variables to that final existential block and use , exactly as for any existential last block. The initial universal block does not alter this local step.
Quick check
(Does -completeness of a problem prove it lies outside ?)
Could the two levels coincide?
Solution · Answer
No. If the levels happened to coincide, a complete problem could also belong to the lower level. Completeness gives reductions from the level, not an unconditional separation.
Quick check
(Why is negating a CNF consistency formula enough to produce a polynomial-size DNF here?)
Apply De Morgan's law to one conjunction.
Solution · Answer
The negation of a conjunction of clauses is a disjunction of the negations of individual clauses. Each negated clause is a term, so no exponential distribution is needed.
Quick check
(For an existential-universal prefix, which matrix form is supplied by the completeness construction: CNF or DNF?)
Look at the final quantifier.
Solution · Answer
DNF, because the final block is universal and the construction uses .
Quick check
(Why can with a CNF matrix be checked in NP?)
Distribute the universal quantifier over the clauses.
Solution · Answer
Guess and test each residual clause for universal tautology. A residual clause is universally true exactly when its existential portion is already true or it contains both a universal literal and its negation.