An NP verifier asks whether there exists a short certificate. Some claims naturally alternate choices: is there a strategy that works against every short response? Quantified polynomial-time predicates formalize such questions without assuming that every quantifier can be eliminated efficiently.
Motivation: from certificates to strategies
A certificate for membership in NP is a single, static object. To convince a skeptic that a Boolean formula is satisfiable, one hands over an assignment, and the skeptic checks it in polynomial time. The skeptic never has to respond to anything, and the prover never has to anticipate the skeptic's objections.
Many natural questions have a different shape. Consider the following:
- Does a given circuit have a setting of its "design" inputs that works for every setting of its "environment" inputs?
- Is there an opening move in a finite game after which every reply of the opponent can be answered so that the first player eventually wins within a polynomial number of rounds?
- Are two Boolean formulas equivalent, meaning that no assignment distinguishes them?
The last question is already familiar. Its negative form, "some assignment distinguishes them," is an NP statement, so equivalence of formulas is a coNP statement. This unit studies what happens when we continue the pattern: one existential block, then a universal block, then an existential block, and so on, always with a fixed number of blocks and a polynomial-time check at the end.
Three themes organize the unit.
- The syntax of the classes: what exactly is allowed in a quantifier block, and why the number of blocks is a constant.
- The algebra of the classes: negation exchanges and , and adding dummy blocks gives nesting. We prove an upper bound by polynomial space; a companion unit proves a conditional collapse statement.
- The semantics of quantifier order: why and are different, and how an existential choice that sits inside a universal quantifier becomes a strategy, that is, a function of the earlier choices.
Quantifier classes
Definition 8.1.1
(Quantified verifier classes)
Let . A language is in if membership can be expressed by alternating blocks of polynomial-length binary strings, starting with an existential block, followed by a deterministic polynomial-time predicate. A language is in if it has the analogous expression starting with a universal block. The polynomial hierarchy is the union of these classes over all fixed . In particular and .
For example, a statement has the form
where is polynomial-time computable. The strings can represent moves in a two-stage game: the existential player chooses knowing , and must succeed for every response . Fixed polynomial lengths are harmless: shorter certificates can be padded in a way the predicate checks.
Exact hypotheses and conventions
The definition above is deliberately informal about lengths, so we fix conventions that make the later proofs precise.
Each block length is a polynomial with nonnegative integer coefficients, so that is computable in time polynomial in . A block variable ranges over all of . This set is never empty, since even for it contains the empty string. This nonemptiness is the only property of the domains used when we add dummy quantifiers. The predicate is computed by a deterministic machine whose running time is bounded by a polynomial in the total input length . Because every is itself polynomial in , this time is also polynomial in alone.
Two harmless normalizations will be used freely.
- Equal block lengths. If the blocks have different lengths , replace each by the polynomial . The predicate computes the original block lengths and ignores the unused padding bits. Because a padded string determines the original one by truncation, and every original string occurs as a truncation, the truth value of the statement is unchanged.
- Adjacent blocks of the same type merge. A pattern is equivalent to a single block over the concatenated string, and likewise for . So only the number of alternations matters, and a statement with several consecutive existential quantifiers has the same level as one with a single quantifier there.
Finally, an expression such as always refers to a fixed integer . The class allows different languages to use different , but no single language is allowed a block count that grows with . Allowing a growing number of blocks is a different setting; for example, fully quantified Boolean formula is PSPACE-complete, a result taken up in the unit on quantified Boolean formulas.
Complement and nesting
Proposition 8.1.2
(Complement and nesting)
For every fixed , the complements of languages are exactly the languages. Also and are each contained in both and .
Proof
(Proof)
Negating a quantified statement swaps each existential quantifier with a universal one and complements the final polynomial-time predicate, proving the first claim in both directions. To increase the number of blocks, add a dummy quantified string ignored by the predicate at the beginning when the opposite starting quantifier is needed, or at the end when the same starting quantifier is needed. Since each quantified domain is nonempty, the dummy block does not change truth. This gives all four containments.
A deterministic polynomial-time predicate with a dummy existential block gives ; a dummy universal block gives . So the levels form a ladder, and contains .
Notice what the proposition does not say. It does not say that , and it does not say that the containments are strict. Both questions are open.
An example
Worked example 8.1.3
(Choosing a robust assignment)
Let the input be a Boolean formula with its variables partitioned into two lists. Ask whether some assignment to makes true for every assignment to . This is in : guess the first assignment, universally quantify the second, and evaluate the formula in polynomial time. For , choosing succeeds. For , neither fixed value of works for both values of .
Order of choices, strategies, and counterexamples
Quantifier order is a real distinction, not a notational one. For every predicate on any nonempty domains,
To see this, suppose satisfies . Given any , the same witnesses . The converse is false.
Counterexample mode
Swapping the quantifiers is not an equivalence
The claim that implies is wrong. On one-bit strings take . For the witness is and for it is , so is true. But is false: fails at and fails at . The two orders therefore define different languages in general. Only the one-way implication above survives; the two statements agree only when a witness can be chosen without looking at .
This explains the word "strategy." In , the witness is a function from values of to values of . In the counterexample above, is the identity, and a single constant value cannot replace it. In the polynomial hierarchy, the strategy may have exponentially large description, since its domain has exponentially many points. That is why statements are not obviously verifiable by a single short certificate, and why adding quantifier blocks can plausibly add expressive power.
A different shortcut also fails. To negate , one must negate every quantifier and the predicate. Negating only the predicate does not give the complement.
Common mistake
(Negating only the predicate)
On one-bit strings, let mean . The statement is false, so its complement is true. But , that is, , is also false: for the value breaks it, and for the value breaks it. So "same quantifiers, complemented predicate" gives the wrong answer here. The correct complement is , which is true by taking .
Evaluating a quantified statement by hand
The next example makes the semantics of quantifier order concrete by evaluating every candidate for the existential block.
Worked example 8.1.4
(A unique robust witness, and its complement)
Let be a two-bit string and a single bit, and put
We decide .
For fixed , evaluate at the two values of .
- For : the first clause is and the second is . So .
- For : the first clause is and the second is . So .
Hence holds exactly when and . Among the four candidates the table reads:
| false | |||
| false | |||
| false | |||
| true |
So the statement is true, and is the unique witness. This took evaluations of in the worst case.
The complement is , a statement, which is false. Reading the table, for each of the three failing there is a refuting : for and take (since ), and for take (since ). For there is none, which is exactly why the complement fails. The refuting choice of genuinely depends on here, in line with the strategy discussion above.
Three blocks and the role of dependence
The following example uses three blocks, so it lives in when are strings. It also shows that moving a quantifier across another one changes the answer.
Worked example 8.1.5
(An existential choice that must depend on a universal one)
Over one-bit variables define
Decide and compare it with .
Case . Then , so . For each , choose , giving . So is true, and the first statement is true with witness .
Case . Then . For this is for every , so is false. Hence is not a witness.
Thus is true, and its winning strategy is together with the function .
For the second statement, the pair is chosen before .
- If , then . A fixed fails at , where .
- If , then , which fails at for every .
So no pair works and the second statement is false. Because the adjacent quantifiers merge into one block, the second statement is a -type pattern. The calculation shows that interleaving a universal quantifier between two existential ones is not harmless: the first statement is true and the second false, for the same predicate.
Evaluation in polynomial space
The brute-force evaluations above suggest an algorithm. It uses very little memory, even though it may take exponential time.
Proposition 8.1.6
(The hierarchy lies inside polynomial space)
For every fixed , . Consequently .
Proof
(Proof)
Let with equal block lengths and predicate , as justified by the conventions above. The case is symmetric, and also follows from the fact that is closed under complement, since consists of complements of languages.
Define a recursive procedure for . If , it runs and returns the result. Otherwise, if block is existential, it enumerates all strings in lexicographic order, calls on each, returns as soon as some call returns , and returns if none does. If block is universal, it returns as soon as some call returns , and returns otherwise.
By induction on , the call returns exactly when the remaining quantified statement holds for that prefix. The base case is correct by definition of . In the inductive step, an existential block returns precisely when some extension succeeds, and a universal block returns precisely when all extensions succeed. So decides .
For space, at most recursive frames are active simultaneously. Each frame stores one current string of bits (which also serves as the enumeration counter) and a constant amount of control information. The leaf call to runs in polynomial time and hence uses polynomial space, and that space is released and reused after each leaf call. The total space is plus a polynomial for , which is polynomial because is fixed.
Proof X-ray
Where the polynomial space comes from
The recursion tree of has depth but up to leaves, so the tree itself is exponentially large. The proof never stores it. A frame is created when a block starts enumerating and discarded when the enumeration ends, so at any moment memory holds only one path from the root to the current node. That is the key move: sibling subtrees are explored one after another and the same bits are reused. Correctness is a separate matter and rests only on the induction. An existential block is an OR over its children and a universal block is an AND, so returning early changes the running time but not the answer.
Two hypotheses are used. The fixed only counts frames: frames of bits each. If the number of blocks grew polynomially with , the same recursion would still need only polynomially many frames of polynomial size, which is why quantified Boolean formulas also lie in . The polynomial running time of bounds the space of a leaf call. The argument says nothing about time: the number of calls is exponential, and no step of the proof gives a time lower bound.
The running time of this procedure is at most times a polynomial, so the proposition gives no efficient algorithm. For example, with and block length , up to evaluations of may occur, while only bits of assignment are stored.
Practice and solutions
Quick check
(Negate the statement and identify the resulting quantifier pattern.)
Swap every quantifier and complement the predicate.
Solution · Answer
The negation is , a universal-then-existential pattern with a polynomial-time complemented predicate.
Quick check
(For one-bit , is true?)
Ask whether the choice of may depend on .
Solution · Answer
It is true: after seeing , choose . This choice can depend on because it occurs inside the universal quantifier.
Further exercises follow. Attempt each before opening the solutions.
Quick check
(Let be given by . Write as a statement and as a statement, saying where the dummy blocks go and why truth is preserved.)
Add blocks that the predicate ignores.
Solution · Answer
For , append two dummy blocks after the existential block: , where the predicate ignores . The pattern is , so it has three alternating blocks starting existentially. For , prepend a dummy universal block: . The pattern is with two blocks. In both cases each added domain is nonempty and the predicate does not depend on it, so for any statement not mentioning .
Exercise 8.1.7
(Decide the truth of over one-bit variables, and write its negation in prenex form.)
Core
Hint(1)
Treat the two values of separately and ask, for each, which could work.
Solution(3)
- 1
Take
The first clause is , so we need a with . Choosing gives for every . So passes.
- 2
Take
Key step
With the first clause is , so fails at once. With the second clause is , which is at . So no works for .
Because: The first clause becomes , which forces .
- 3
Decide the statement and negate it
The statement requires every to pass, so it is false, witnessed by . Its negation in prenex form is
which is true: take ; for the first clause already fails, and for take .
Exercise 8.1.8
(Prove that for each the class is closed under intersection.)
SynthesisProof
Hint(1)
Run the two statements side by side, pairing their blocks.
Solution(4)
- 1
Pad both statements to one block length
Let have predicates . By the equal-length convention both use blocks of one length . They read and , with alternating and .
- 2
Define the combined statement
Put , which is polynomial-time computable. Let block range over pairs with the same quantifier . This is a statement with alternating blocks starting with .
- 3
Separate the two families of variables
Key step
If does not mention and does not mention , then for . Apply this to the innermost pair , then to , and so on outward. At each stage the part already separated no longer mentions the variables being pulled out.
Because: The domains are nonempty and neither conjunct mentions the other's variables.
- 4
Read off the language
∎After stages the combined statement is equivalent to . Its language is , and it lies in . Replacing by gives closure under union in the same way.
Quick check
(A statement has both blocks of length . In the worst case, how many evaluations of the predicate can the recursive procedure perform, and how many assignment bits does it store?)
Count the pairs .
Solution · Answer
The procedure evaluates the predicate at most once per pair , so at most times. It stores one string per active block, which is assignment bits, plus the workspace of the predicate and constant-size control information. Early termination can reduce the count. The bound is attained if every candidate except the last fails only at its last , while the last succeeds for every .