Motivation
A randomized algorithm with bounded error must keep a visible gap between acceptance and rejection probabilities. What if the acceptance probability is only infinitesimally above one half, but the sign of that difference is guaranteed to be correct? The class PP studies exactly this situation. Counting acceptance paths makes the definition precise and reveals why ordinary sampling cannot automatically decide such a tiny difference in polynomial time.
All probabilities in this unit are for a fixed input . A polynomial-time randomized machine uses independent uniform bits. By padding with unused bits, we may assume that on every input of length it reads exactly random bits for one fixed polynomial with integer values. Each random string has probability , even when several strings lead to identical computation histories. Counting strings rather than distinct histories is essential to the probability calculation.
Strict majority and counting paths
A language is in if there is a polynomial-time randomized machine such that
The strict inequality is part of the definition. On a no-instance the acceptance probability may equal exactly. The machine need not have any inverse-polynomial gap from ; with random bits the smallest positive change in the acceptance probability can be .
For a fixed input put
Then . The PP condition says , interpreted directly as a probability inequality when . The integer counts accepting random strings, including strings that the machine padded but did not inspect.
Worked example 5.2.1
(A tie is a no-instance under this convention)
Suppose a machine uses three random bits. If it accepts on five of the eight strings, its acceptance probability is . If it accepts on four, the probability is exactly , so the strict-majority predicate answers no. If it accepts on three, the answer is also no. Changing a convention from to without addressing ties can change the language recognized by that particular machine.
Common mistake
(A majority is not necessarily a robust majority)
An acceptance probability of is above , but the advantage may be exponentially small. A BPP-style proof based on a constant gap and a polynomial number of independent samples cannot simply be reused. PP is a definition of which side of the threshold the exact probability lies on; it does not assert that an efficient experiment estimates that sign.
Counting witnesses and threshold predicates
A function is in in the witness formulation if there are a polynomial and a deterministic polynomial-time predicate such that
Messages of shorter length can be encoded in fixed-length strings using an unambiguous length convention. The witness count is a nonnegative integer, not a decision bit. Normalizing the branching of a nondeterministic machine to this witness form is a standard background equivalence; we use the displayed form directly.
Proposition 5.2.2
(PP as a threshold on a witness count)
A language is in PP exactly when there are a function represented by witness bits and a polynomial-time computable padding convention for which
Proof
(Proof)
Given a PP machine with random bits, take to simulate that machine with as its random string. If can be zero, append one unused random bit. Appending doubles both the number of strings and the number that accept, preserving whether the fraction is strictly above one half. The resulting count is in and obeys the displayed threshold.
Conversely, given the displayed witness predicate, sample uniformly from and accept exactly when . The acceptance probability is , which is greater than one half exactly on . Both sampling and verification take polynomial time. The padding convention fixes the length uniformly for each input length; it does not alter the strict threshold.
Worked example 5.2.3
(Counting assignments on a declared variable list)
For , three of the four assignments satisfy the formula. Sampling a uniform assignment therefore accepts with probability , above one half. For , exactly two assignments satisfy it, giving a tie. The declared list matters: adding an unused variable doubles both the count and the total number of assignments, leaving the fraction unchanged. Adding a variable is not the same operation as merely changing the claimed count while holding the denominator fixed.
Worked example 5.2.4
(A gap of one accepting string)
Let . A machine accepting on of its random strings has probability . Another accepting on strings is exactly tied. As grows polynomially with input length, a one-string difference yields an exponentially small probability gap. Exact counting distinguishes these cases immediately in principle, while a small empirical sample can easily look the same in both.
NP and bounded-error randomized computation
Theorem 5.2.5
(NP and BPP are contained in PP)
and .
Proof
(Proof)
For BPP, use a bounded-error decider with acceptance probability at least on yes-instances and at most on no-instances. These probabilities lie on the correct sides of , so the same machine is a PP machine.
For NP, let verify witnesses of length . Draw an independent fair bit and a uniform -bit string . If , accept immediately. If , accept exactly when . When no witness exists, the acceptance probability is exactly . When at least one witness exists, the second branch contributes a positive amount, so the acceptance probability is strictly above . The construction is polynomial time even if only one of exponentially many witnesses works. Thus the strict threshold correctly distinguishes the two cases.
Worked example 5.2.6
(One witness can tilt an exact majority)
Suppose there are eight candidate witnesses and exactly one passes the verifier. In the NP-to-PP construction, the immediate-accept branch contributes eight accepting pairs and the verification branch contributes one more, for nine accepting strings among sixteen. If there are no witnesses, there are exactly eight accepting strings among sixteen, a tie. The construction does not locate the witness; it encodes its existence in the sign of a small probability difference.
Neither containment proves that PP has an efficient bounded-error algorithm. The NP construction can have an exponentially small advantage, and the BPP containment is only one direction. Known or conjectured separations among these classes require additional arguments; none is asserted here.
Complementing a strict majority
Flipping the output of a PP machine is not enough to complement its language, because of ties.
Counterexample mode
Swapping the outputs does not complement a PP language
Suppose one claims that swapping the accepting and rejecting outputs of a PP machine gives a machine for the complement of . Take an input on which uses one random bit and accepts exactly when . It accepts on of strings, probability exactly , so . The swapped machine accepts exactly when , again on of strings, so it also rejects under the strict-majority rule. Thus lies outside both and the language of the swapped machine, which therefore is not the complement of . The repair is to move ties to the accepting side, as the next construction does.
The following padding construction resolves the boundary without assuming a gap.
Theorem 5.2.7
(PP is closed under complement)
If , then its complement belongs to PP.
Proof
(Proof)
Pad the original PP machine so that it uses random bits. Write and let be the number of its accepting random strings on . Add two independent random bits and reuse the -bit string . Define the new machine by these four cases:
- If is or , accept exactly when the original machine rejects on .
- If , always accept.
- If , accept exactly when .
There are equally likely strings altogether. The first two cases contribute accepting strings, the third contributes , and the last contributes one. Hence the new machine accepts on strings. Its strict-majority condition is
Since is even and is an integer, this inequality holds exactly when . That is precisely the condition that the original machine does not accept with probability strictly greater than one half. All extra tests and simulations take polynomial time, so the new machine recognizes the complement in PP.
Proof X-ray
What the single extra string does
Changing the original count by one changes the new count by two. The terms and place the threshold exactly at : the new count equals , a tie, precisely when . The final case adds one more accepting string, and one is smaller than the step of two, so it changes the verdict only at the tie , turning it into acceptance, and leaves every non-tied value of on the same side as before. The padding to makes even, so that the tie value is an integer and can actually occur. Without the extra string the construction would reproduce the failure of simple swapping; with a bonus of three or more strings it would also accept , a yes-instance of the original machine.
Worked example 5.2.8
(Checking the boundary case)
Take and original count . The complement construction has accepting strings out of , so it accepts strictly more than half. If , the new count is out of and it rejects by the PP convention. The extra single accepting string resolves the tie; simply reversing every original answer would have left accepting strings out of eight in the first case.
Concept lensAlgebraic
PP as the sign of a signed sum
Give each random string the value if accepts and if it rejects, and let . Then exactly when , so PP asks for the sign of an integer-valued sum, with a tie meaning . In this form the complement construction is the identity : since is even, exactly when .
By complement closure and NP containment, as well. Complement closure establishes . It does not establish , which remains an independent question.
A deterministic space upper bound
Exact counting can take exponential time and still use polynomial space. Enumerate every possible random string in lexicographic order, simulate the polynomial-time machine on that string, and keep a binary counter for the number of accepting strings. The enumeration index needs bits and the count needs at most bits. One simulation uses polynomial space because it takes polynomial time, and its workspace is reused for the next random string.
Proposition 5.2.9
(PP lies in polynomial space)
.
Proof
(Proof)
For input , compute the common random-string length and enumerate all strings with an -bit counter. Simulate the PP machine separately on each string and increment an -bit acceptance counter when it accepts. At the end compare the count with , or compare twice the count with to handle uniformly. The work tape stores the two counters and one polynomial-space simulation, all polynomial in . The algorithm terminates after exponentially many simulations, so it decides the language in polynomial space; no polynomial-time bound follows from this enumeration.
Worked example 5.2.10
(A counter can be short while enumeration is long)
With random bits there are strings. An index needs bits and an acceptance counter needs bits, even though the machine may need to perform more than a million simulations. With , the same counters have polynomial length while the number of simulated strings is . Space is reused; time accumulates.
What the counting viewpoint does and does not prove
The permanent of a matrix, its -completeness under a specified reduction notion, and Toda's theorem relating the polynomial hierarchy to counting are major further results. They are not proved here. A completeness statement must name its reduction and input encoding; an oracle statement involving a counting function must likewise specify how the count is returned and charged. The simple threshold characterization above should not be mistaken for a proof of any of these deeper results.
A count can be computed by enumerating all witnesses in polynomial space, just as above, but the result may have exponentially many possible values and requires a suitable output convention. Conversely, knowing only whether the count is nonzero is an NP-style decision question and generally reveals less information than the exact count. Counting witnesses, deciding existence, and comparing against half are three different tasks even when they use the same verifier.
Practice and solutions
Quick check
(A machine uses four random bits and accepts on eight strings. Does it meet the strict PP threshold on this input?)
Compare the acceptance probability with .
Solution · Answer
No. There are sixteen strings and acceptance probability ; the definition requires a strict inequality.
Quick check
(In the NP-to-PP construction, what is the acceptance probability when there are no witnesses? What changes if at least one witness exists?)
Separate the two branches of the construction.
Solution · Answer
It is exactly with no witnesses. At least one witness adds a positive probability in the verification branch, making the probability strictly greater than .
Quick check
(If a PP machine uses bits and accepts on strings, how many strings does the complement construction accept?)
Use the count with .
Solution · Answer
Here , so the count is out of . Since , the original is on the no side and the complement is on the yes side.
Quick check
(Why does flipping the output of a machine fail to handle a tie?)
What does a tie look like after the flip?
Solution · Answer
If the original accepts on exactly half of the strings, its flipped output also accepts on exactly half. Both would be no under a strict-majority definition.
Quick check
(How much space is needed to index all random strings and count accepting ones?)
Count the bits of the index and of the counter separately.
Solution · Answer
The index needs bits and the count at most bits; a polynomial-space simulation is reused for each string.
Quick check
(Does the containment of PP in PSPACE imply a polynomial-time simulation?)
Compare the number of sequential steps with the space used.
Solution · Answer
No. The construction may enumerate exponentially many random strings. Polynomial space bounds simultaneous storage, not the number of sequential steps.