A class inspired by the proverb, "if at first you don't succeed, try, try again."
Formally, the class of decision problems solvable by a BQP machine such that
Defined in [Aar05b], where it is also shown that PostBQP equals PP.
[Aar05b] also gives the following alternate characterizations of PostBQP (and therefore of PP):
Literally, the class of ALL languages.
ALL is a gargantuan beast that's been wreaking havoc in the Zoo of late.
First [Aar04b] observed that PP/rpoly (PP with polynomial-size randomized advice) equals ALL, as does PostBQP/qpoly (PostBQP with polynomial-size quantum advice).
Then [Raz05] showed that QIP/qpoly, and even IP(2)/rpoly, equal ALL.
Nor is it hard to show that MAEXP/rpoly = ALL.
Also, per [Aar18], PDQP/qpoly = ALL.
On the other hand, even though PSPACE contains PP, and EXPSPACE contains MAEXP, it's easy to see that PSPACE/rpoly = PSPACE/poly and EXPSPACE/rpoly = EXPSPACE/poly are not ALL.
So does ALL have no respect for complexity class inclusions at ALL? (Sorry.)
It is not as contradictory as it first seems. The deterministic base class in all of these examples is modified by computational non-determinism after it is modified by advice. For example, MAEXP/rpoly means M(AEXP/rpoly), while (MAEXP)/rpoly equals MAEXP/poly by a standard argument. In other words, it's only the verifier, not the prover or post-selector, who receives the randomized or quantum advice. The prover knows a description of the advice state, but not its measured values. Modification by /rpoly does preserve class inclusions when it is applied after other changes.
Same as BPP, except that now the computation paths need not all have the same length.
Defined in [HHT97], where the following was also shown:
There exists an oracle relative to which BPPpath is not contained in Σ2P [BGM02].
An alternate characterization of BPPpath uses the idea of post-selection. That is, BPPpath is the class of languages for which there exists a pair of polynomial-time Turing machines and such that the following conditions hold for all :
We say that is the post-selector. Intuitively, this characterization allows a BPP machine to require that its random bits have some special but easily verifiable property. This characterization makes the inclusion NP ⊆ BPPpath nearly trivial.
See Also: PostBQP (quantum analogue).
The class of decision problems solvable by an NP machine such that
Defined in [Gil77].
PP is closed under union and intersection [BRS91] (this was an open problem for 14 years). More generally, PPP[log] = PP. Even more generally, PP is closed under polynomial-time truth-table reductions, or even k-round reductions for any constant k [FR96].
Contains PNP[log] [BHW89] and QMA (see [MW05]). However, there exists an oracle relative to which PP does not contain Δ2P [Bei94].
BPP [KST+89b] and even BQP [FR98] and YQP* [Yir24] are low for PP: i.e., PPBQP = PP.
APP is PP-low [Li93].
For a random oracle A, PPA is strictly contained in PSPACEA with probability 1 [ABF+94].
For any fixed k, there exists a language in PP that does not have circuits of size nk [Vin04b].
Indeed, there exists a language in PP that does not even have quantum circuits of size nk with quantum advice [Aar06] and [Yir24].
By contrast, there exists an oracle relative to which PP has linear-size circuits [Aar06].
PP can be generalized to the counting hierarchy CH.
The class of decision problems solvable in polynomial time by a quantum Turing machine, with less than 1/2 probability of error.Similar to BQP in definition, but without bounded error.
Defined in [Wat09], where it shown to be equivalent to PP.
Equals PP and therefore PPBPP [KST+89b] as well as PostBQP [Aar05b].