From Qwiki

Introduction

Welcome to the Complexity Zoo... There are now 460 classes and counting!

This information was originally moved from http://www.complexityzoo.com/ in August 2005, and is currently under the watchful eyes of its original creators:

Zookeeper: Scott Aaronson
Veterinarian: Greg Kuperberg

Errors? Omissions? Misattributions? Your favorite class not here? Then please contribute to the zoo as you see fit by signing up and clicking on the edit links. Please include references, or better yet links to papers if available.

To create a new class, click on the edit link of the class before or after the one that you want to add and copy the format of that class. (The classes are alphabetized by their tag names.) Then add the class to the table of contents and increment the total number of classes. After this, you can use the side edit links to edit the individual sections. For more on using the wiki language, see our simple wiki help page.

If you would like to contribute but feel unable to make the updates yourself, email the zookeeper at scott at scottaaronson dot com.

See Also

• Introductory Essay
• Glossary
• Pronunciation Guide
• References
• Special Zoo Exhibit
• Acknowledgments
• **New** Complexity Zoology, a computer-assisted survey, with active and static inclusion diagrams.

(Longtime Zoo watchers may recall Chris Bourke's LaTeX version of the Zoo and Chad Brewbaker's graphical inclusion diagram. These references are obsolete until further notice.)

Table of Contents

∅: 0-1-NP_C - 1NAuxPDA^p - #AC⁰ - #L - #L/poly - #GA - #P - #W[t] - ⊕EXP - ⊕L - ⊕L/poly - ⊕P - ⊕SAC⁰ - ⊕SAC¹

A: A₀PP - AC - AC⁰ - AC⁰[m] - AC¹ - ACC⁰ - AH - AL - ALL - AlgP/poly - Almost-NP - Almost-P - Almost-PSPACE - AM - AM_EXP - AM ∩ coAM - AM[polylog] - AmpMP - AmpP-BQP - AP - APP - APX - AUC-SPACE(f(n)) - AuxPDA - AVBPP - AvgE - AvgP - AW[P] - AWPP - AW[SAT] - AW[*] - AW[t] - AxP - AxPP

B: βP - BH - BPE - BPEE - BP_HSPACE(f(n)) - BPL - BP•NP - BPP - BPP^cc - BPP^KT - BPP/log - BPP/mlog - BPP//log - BPP/rlog - BPP-OBDD - BPP_path - BPQP - BPSPACE(f(n)) - BPTIME(f(n)) - BQNC - BQNP - BQP - BQP/log - BQP/poly - BQP/mlog - BQP/mpoly - BQP/qlog - BQP/qpoly - BQP-OBDD - BQPSPACE - BQP_tt/poly - BQTIME(f(n)) - k-BWBP

C: C₌AC⁰ - C₌L - C₌P - CFL - CLOG - CH - Check - CL#P - C_kP - CNP - coAM - coC₌P - cofrIP - Coh - coMA - coMod_kP - compIP - compNP - coNE - coNEXP - coNL - coNP - coNP^cc - coNP/poly - coNQP - coRE - coRNC - coRP - coSL - coSPARSE - coUCC - coUP - CP - CSIZE(f(n)) - CSL - CZK

D: D#P - DCFL - Δ₂P - δ-BPP - δ-RP - DET - DiffAC⁰ - DisNP - DistNP - DP - DQP - DSPACE(f(n)) - DTIME(f(n)) - DTISP(t(n),s(n)) - Dyn-FO - Dyn-ThC⁰

E: E - EE - EEE - EESPACE - EEXP - EH - ELEMENTARY - EL_kP - EP - EPTAS - k-EQBP - EQP - EQP_K - EQTIME(f(n)) - ESPACE - ∃BPP - ∃NISZK - EXP - EXP/poly - EXPSPACE

F: FBQP - Few - FewP - FH - FNL - FNL/poly - FNP - FO(t(n)) - FOLL - FP - FP^NP[log] - FPR - FPRAS - FPT - FPT_nu - FPT_su - FPTAS - FQMA - frIP - F-TAPE(f(n)) - F-TIME(f(n))

G: GA - GAN-SPACE(f(n)) - GapAC⁰ - GapL - GapP - GC(s(n),C) - GCSL - GI - GLO - GPCD(r(n),q(n)) - G[t]

H: HalfP - HeurBPP - HeurBPTIME(f(n)) - H_kP - HVSZK

I: IC[log,poly] - IP - IPP - IP[polylog]

L: L - LIN - L_kP - LOGCFL - LogFew - LogFewNL - LOGNP - LOGSNP - L/poly - LWPP

M: MA - MA' - MAC⁰ - MA_E - MA_EXP - mAL - MaxNP - MaxPB - MaxSNP - MaxSNP₀ - mcoNL - MinPB - MIP - MIP*[2,1] - MIP_EXP - (M_k)P - mL - mNC¹ - mNL - mNP - Mod_kL - Mod_kP - ModP - ModZ_kL - mP - MP - MPC - mP/poly - mTC⁰

N: NAuxPDA^p - NC - NC⁰ - NC¹ - NC² - NE - NE/poly - Nearly-P - NEE - NEEE - NEEXP - NEXP - NEXP/poly - NIQSZK - NISZK - NISZK_h - NL - NL/poly - NLIN - NLOG - NONE - NP - NPC - NP_C - NP^cc - NPI - NP ∩ coNP - (NP ∩ coNP)/poly - NP/log - NPMV - NPMV-sel - NPMV_t - NPMV_t-sel - NPO - NPOPB - NP/poly - (NP,P-samplable) - NP_R - NPSPACE - NPSV - NPSV-sel - NPSV_t - NPSV_t-sel - NQP - NSPACE(f(n)) - NT - NT* - NTIME(f(n))

O: OCQ - OptP

P: P - P/log - P/poly - P^#P - P^#P[1] - PAC⁰ - PBP - k-PBP - P_C - P^cc - PCD(r(n),q(n)) - P-Close - PCP(r(n),q(n)) - PermUP - PEXP - PF - PFCHK(t(n)) - PH - PH^cc - Φ₂P - PhP - Π₂P - PINC - PIO - P^K - PKC - PL - PL₁ - PL_∞ - PLF - PLL - PLS - P^NP - P^||NP - P^NP[k] - P^NP[log] - P^{NP[log^2]} - P-OBDD - PODN - polyL - PostBQP - PP - PP/poly - PPA - PPAD - PPADS - P^PP - PPP - PPSPACE - PQUERY - PR - P_R - Pr_HSPACE(f(n)) - PromiseBPP - PromiseBQP - PromiseP - PromiseRP - PrSPACE(f(n)) - P-Sel - PSK - PSPACE - PSPACE/poly - PT₁ - PTAPE - PTAS - PT/WK(f(n),g(n)) - PZK

Q: Q - QAC⁰ - QAC⁰[m] - QACC⁰ - QAC_f⁰ - QAM - QCFL - QCMA - QH - QIP - QIP[2] - QMA - QMA-plus - QMA(2) - QMA_log - QMAM - QMA/qpoly - QMIP - QMIP_le - QMIP_ne - QNC - QNC⁰ - QNC_f⁰ - QNC¹ - QP - QPLIN - QPSPACE - QRG - QS₂P - QSZK

R: R - RBQP - RE - REG - RevSPACE(f(n)) - RG - RG[1] - R_HL - R_HSPACE(f(n)) - RL - RNC - RP - RPP - RQP - RSPACE(f(n))

S: S₂P - S₂-EXP•P^NP - SAC - SAC⁰ - SAC¹ - SAPTIME - SBP - SC - SE - SEH - SelfNP - SF_k - Σ₂P - SKC - SL - SLICEWISE PSPACE - SNP - SO-E - SP - span-P - SPARSE - SPL - SPP - SQG - SUBEXP - symP - SZK - SZK_h

T: TALLY - TC⁰ - TFNP - Θ₂P - TreeBQP - TREE-REGULAR

U: UAP - UCC - UE - UL - UL/poly - UP - US

V: VNC_k - VNP_k - VP_k - VQP_k

W: W[1] - WAPP - W[P] - WPP - W[SAT] - W[*] - W[t] - W^*[t]

X: XOR-MIP*[2,1] - XP - XP_uniform

Y: YACC - YP - YPP - YQP

Z: ZBQP - ZPE - ZPP - ZPTIME(f(n)) - ZQP

The Classes

Warning: Please do not feed oracles to the complexity classes! These classes require a specially balanced diet to ensure proper relativization.

---

0-1-NP_C: Binary Restriction of NP Over The Complex Numbers

The intersection of NP_C with {0,1}^* (i.e. the set of binary strings).

Contains NP.

Is contained in PSPACE, and in AM assuming the Extended Riemann Hypothesis [Koi96].

---

1NAuxPDA^p: One-Way NAuxPDA^p

Defined in [Bra77], where it was also shown that 1NAuxPDA^p strictly contains CFL and is strictly contained in LOGCFL. The class corresponds to the closure of CFL under one-way log-space reductions.

---

#AC⁰: Sharp-AC⁰

The class of functions from {0,1}ⁿ to nonnegative integers computed by polynomial-size constant-depth arithmetic circuits, using addition and multiplication gates and the constants 0 and 1.

Contained in GapAC⁰.

---

#GA: Graph Automorphism

The class of problems (Karp-)reducible to counting the number of automorphisms of a graph.

Counterpart of GI.

---

#L: Sharp-L

Has the same relation to L as #P does to P.

#L is contained in DET [AJ93].

---

#L/poly: Nonuniform #L

Has the same relation to #L as P/poly does to P.

---

#P: Sharp-P

The class of function problems of the form "compute f(x)," where f is the number of accepting paths of an NP machine.

The canonical #P-complete problem is #SAT: given a Boolean formula, compute how many satisfying assignments it has.

Defined in [Val79], where it was also shown that the problem of counting the number of perfect matchings in a bipartite graph (or equivalently, computing the permanent of a 0-1 matrix) is #P-complete.

What makes that interesting is that the associated decision problem (whether a bipartite graph has a perfect matching) is in P.

PH is in P^#P [Tod89].

Any function in #P can be approximated to within a polynomial factor in BPP with NP oracle [Sto85].

---

#W[t]: Sharp-W[t]

Roughly, the analogue of #P for parameterized complexity. I.e. the class of parameterized counting problems that are fixed-parameter parsimonious reducible to the following problem:

#WSAT: Given a Boolean formula, count the number of satisfying assignments of Hamming weight k (where k is the parameter).

Defined in [FG02], which should be consulted for the full definition. [FG02] also showed that there exist #W[1]-complete problems whose corresponding decision problems are fixed-parameter tractable (i.e. in FPT).

---

⊕EXP: Parity EXP

The exponential-time analogue of ⊕P.

There exists an oracle relative to which ⊕EXP = ZPP [BBF98].

---

⊕L: Parity L

Has the same relation to L as ⊕P does to P.

Contains SL [KW93].

Solving a linear system over Z₂ is complete for ⊕L [Dam90].

⊕L^⊕L = ⊕L [HRV00].

---

⊕L/poly: Nonuniform ⊕L

Has the same relation to ⊕L as P/poly does to P.

Contains NL/poly [GW96].

---

⊕P: Parity P

The class of decision problems solvable by an NP machine such that

1. If the answer is 'yes,' then the number of accepting paths is odd.
2. If the answer is 'no,' then the number of accepting paths is even.

Defined in [PZ83].

Contains graph isomorphism; indeed, graph isomorphism is low for ⊕P [AK02].

Contains FewP [CH89].

There exists an oracle relative to which P = ⊕P but P is not equal to NP (and indeed NP = EXP) [BBF98].

Equals Mod_2^mP for every positive integer m.

---

⊕SAC⁰: AC⁰ With Unbounded Parity Gates

---

⊕SAC¹: AC¹ With Unbounded Parity Gates

The class of problems solvable by a nonuniform family of polynomial-size, polylog-depth circuits with unbounded-fanin XOR and bounded-fanin AND gates.

Defined in [GW96], where it was also shown that ⊕SAC¹ contains SAC¹.

---

A₀PP: One-Sided Analog of AWPP

Same as SBP, except that f is a GapP rather than #P function.

Defined in [Vya03], where the following was also shown:

• A₀PP contains QMA, AWPP, and coC₌P.
• A₀PP is contained in PP.
• If A₀PP = PP then PH is contained in PP.

---

AC: Unbounded Fanin Polylogarithmic-Depth Circuits

ACⁱ is the class of decision problems solvable by a nonuniform family of Boolean circuits, with polynomial size, depth O(logⁱ(n)), and unbounded fanin. The gates allowed are AND, OR, and NOT.

Then AC is the union of ACⁱ over all nonnegative i.

ACⁱ is contained in NCⁱ⁺¹; thus, AC = NC.

Contains NL.

For a random oracle A, (ACⁱ)^A is strictly contained in (ACⁱ⁺¹)^A, and (uniform) AC^A is strictly contained in P^A, with probability 1 [Mil92].

---

AC⁰: Unbounded Fanin Constant-Depth Circuits

An especially important subclass of AC, corresponding to constant-depth, unbounded-fanin, polynomial-size circuits with AND, OR, and NOT gates.

Computing the parity or majority of n bits is not in AC⁰ [FSS84].

There are functions in AC⁰ that are pseudorandom for all statistical tests in AC⁰ [NW94]. But there are no functions in AC⁰ that are pseudorandom for all statistical tests in QP (quasipolynomial time) [LMN93].

[LMN93] showed furthermore that functions with AC⁰ circuits of depth d are learnable in QP, given their outputs on O(2^{log(n)^O(d)}) randomly chosen inputs. On the other hand, this learning algorithm is essentially optimal, unless there is a 2^{n^o(1)} algorithm for factoring [Kha93].

Although there are no good pseudorandom functions in AC⁰, [IN96] showed that there are pseudorandom generators that stretch n bits to n+Θ(log n), assuming the hardness of a problem based on subset sum.

AC⁰ contains NC⁰, and is contained in QAC⁰ and MAC⁰.

In descriptive complexity, uniform AC⁰ can be characterized as the class of problems expressible by first-order predicates with addition and multiplication operators - or indeed, with ordering and multiplication, or ordering and division (see [Lee02]).

[BLM+98] showed the following problem is complete for depth-k AC⁰ circuits (with a uniformity condition):

Given a grid graph of polynomial length and width k, decide whether there is a path between vertices s and t (which can be given as part of the input).

---

AC⁰[m]: AC⁰ With MOD m Gates

Same as AC⁰, but now "MOD m" gates (for a specific m) are allowed in addition to AND, OR, and NOT gates. (A MOD m gate outputs 0 if the sum of its inputs is congruent to 0 modulo m, and 1 otherwise.)

If m is a power of a prime p, then for any prime q not equal to p, deciding whether the sum of n bits is congruent to 0 modulo q is not in AC⁰[m] [Raz87] [Smo87]. It follows that, for any such m, AC⁰[m] is strictly contained in NC¹.

However, if m is a product of distinct primes (i.e. 6), then it is not even known whether AC⁰[m] = NP!

See also: QAC⁰[m].

---

AC¹: Unbounded Fanin Log-Depth Circuits

See AC.

---

ACC⁰: AC⁰ With Arbitrary MOD Gates

Same as AC⁰[m], but now the constant-depth circuit can contain MOD m gates for any m.

Contained in TC⁰.

Indeed, can be simulated by depth-3 threshold circuits of quasipolynomial size [Yao90].

According to [All96], there is no good evidence for the existence of cryptographically secure functions in ACC⁰. On the other hand, no nontrivial lower bounds against ACC⁰ are known either. Thus, this class represents the current frontier for circuit lower bounds.

Contains 4-PBP [BT88].

See also: QACC⁰.

---

AH: Arithmetic Hierarchy

The analog of PH in computability theory.

Let Δ₀ = Σ₀ = Π₀ = R. Then for i>0, let

• Δ_i = R with Σ_i-1 oracle.
• Σ_i = RE with Σ_i-1 oracle.
• Π_i = coRE with Σ_i-1 oracle.

Then AH is the union of these classes for all nonnegative constant i.

Each level of AH strictly contains the levels below it.

---

AL: Alternating L

Same as AP, but for logarithmic-space instead of polynomial-time.

AL = P [CKS81].

---

ALL: The Class of All Languages

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 MA_EXP/rpoly = ALL.

On the other hand, even though PSPACE contains PP, and EXPSPACE contains MA_EXP, 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, MA_EXP/rpoly means M(A_EXP/rpoly), while (MA_EXP)/rpoly equals MA_EXP/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.

---

AlgP/poly: Polynomial-Size Algebraic Circuits

The class of multivariate polynomials over the integers that can be evaluated using a polynomial (in the input size n) number of additions, subtractions, and multiplications, together with the constants -1 and 1. The class is nonuniform, in the sense that the polynomial for each input size n can be completely different.

Named in [Imp02], though it has been considered since the 1970's.

If P = BPP (or even BPP is contained in NE), then either NEXP is not in P/poly, or else the permanent polynomial of a matrix is not in AlgP/poly [KI02].

---

Almost-NP: Languages Almost Surely in NP^A

The class of problems that are in NP^A with probability 1, where A is an oracle chosen uniformly at random.

Equals AM [NW94].

---

Almost-P: Languages Almost Surely in P^A

The class of problems that are in P^A with probability 1, where A is an oracle chosen uniformly at random.

Equals BPP [BG81].

---

Almost-PSPACE: Languages Almost Surely in PSPACE^A

The class of problems that are in PSPACE^A with probability 1, where A is an oracle chosen uniformly at random.

Almost-PSPACE is not known to equal PSPACE -- rather surprisingly, given the fact that PSPACE equals BPPSPACE and even PPSPACE.

What's known is that Almost-PSPACE = BP^exp•PSPACE, where BP^exp• is like the BP• operator but with exponentially-long strings [BVW98]. It follows that Almost-PSPACE is contained in NEXP^NP ∩ coNEXP^NP.

Whereas both BP^exp•PSPACE and BPPSPACE machines are allowed exponentially many random bits, the former has a reusable record of all of these bits on a witness tape, while the latter can only preserve a fraction of them on the work tape.

---

AM: Arthur-Merlin

The class of decision problems for which a "yes" answer can be verified by an Arthur-Merlin protocol, as follows.

Arthur, a BPP (i.e. probabilistic polynomial-time) verifier, generates a "challenge" based on the input, and sends it together with his random coins to Merlin. Merlin sends back a response, and then Arthur decides whether to accept. Given an algorithm for Arthur, we require that

1. If the answer is "yes," then Merlin can act in such a way that Arthur accepts with probability at least 2/3 (over the choice of Arthur's random bits).
2. If the answer is "no," then however Merlin acts, Arthur will reject with probability at least 2/3.

Surprisingly, it turns out that such a system is just as powerful as a private-coin one, in which Arthur does not need to send his random coins to Merlin [GS86]. So, Arthur never needs to hide information from Merlin.

Furthermore, define AM[k] similarly to AM, except that Arthur and Merlin have k rounds of interaction. Then for all constant k>2, AM[k] = AM[2] = AM [BM88]. Also, the result of [GS86] can then be stated as follows: IP[k] is contained in AM[k+2] for every k (constant or non-constant).

AM contains graph nonisomorphism.

Contains NP, BPP, and SZK, and is contained in Π₂P and NP/poly.

If AM contains coNP then PH collapses to Σ₂P ∩ Π₂P [BHZ87].

There exists an oracle relative to which AM is not contained in PP [Ver92].

AM = NP under a strong derandomization assumption: namely that some language in NE ∩ coNE requires nondeterministic circuits of size 2^Ω(n) ([MV99], improving [KM99]). (A nondeterministic circuit C has two inputs, x and y, and accepts on x if there exists a y such that C(x,y)=1.)

---

AM_EXP: Exponential-Time AM

Same as AM, except that Arthur is exponential-time and can exchange exponentially long messages with Merlin.

Contains MA_EXP, and is contained in EH and indeed S₂-EXP•P^NP.

If coNP is contained in AM[polylog] then EH collapses to AM_EXP [PV04].

---

AM ∩ coAM

The class of decision problems for which both "yes" and "no" answers can be verified by an AM protocol.

If EXP requires exponential time even for AM protocols, then AM ∩ coAM = NP ∩ coNP [GST03].

There exists an oracle relative to which AM ∩ coAM is not contained in PP [Ver95].

---

AM[polylog]: AM With Polylog Rounds

Same as AM, except that we allow polylog(n) rounds of interaction between Arthur and Merlin instead of a constant number.

Not much is known about AM[polylog] -- for example, whether it sits in PH. However, [SS04] show that if AM[polylog] contains coNP, then EH collapses to S₂-EXP•P^NP. ([PV04] improved the collapse to AM_EXP.)

---

AmpMP: Amplifiable MP

The class of decision problems such that for some #P function f(x,0^m),

1. The answer on input x is 'yes' if and only if the middle bit of f(x) is 1.
2. The m bits of f(x) to the left and right of the middle bit are all 0.

Defined in [GKR+95].

Contains PH and Contained in MP.

---

AmpP-BQP: BQP Restricted To AmpP States

Similar to TreeBQP except that the quantum computer's state at each time step is restricted to being exponentially close to a state in AmpP (that is, a state for which the amplitudes are computable by a classical polynomial-size circuit).

Defined in [Aar03b], where it was also observed that AmpP-BQP is contained in the third level of PH, just as TreeBQP is.

---

AP: Alternating P

An alternating Turing machine is a nondeterministic machine with two kinds of states, AND states and OR states. It accepts if and only if the tree of all computation paths, considered as an AND-OR tree, evaluates to 1. (Here 'Accept' corresponds to 1 and 'Reject' to 0.)

Then AP is the class of decision problems solvable in polynomial time by an alternating Turing machine.

AP = PSPACE [CKS81].

The abbreviation AP is also used for Approximable in Polynomial Time, see AxP.

---

APP: Amplified PP

Roughly, the class of decision problems for which the following holds. For all polynomials p(n), there exist GapP functions f and g such that for all inputs x with n=|x|,

1. If the answer is "yes" then 1 > f(x)/g(1ⁿ) > 1-2^-p(n).
2. If the answer is "no" then 0 < f(x)/g(1ⁿ) < 2^-p(n).

Defined in [Li93], where the following was also shown:

• APP is contained in PP, and indeed is low for PP.
• APP is closed under intersection, union, and complement.

APP contains AWPP [Fen02].

The abbreviation APP is also used for Approximable in Probabilistic Polynomial Time, see AxPP.

---

APX: Approximable

The subclass of NPO problems that admit constant-factor approximation algorithms. (I.e., there is a polynomial-time algorithm that is guaranteed to find a solution within a constant factor of the optimum cost.)

Contains PTAS.

Equals the closure of MaxSNP and of MaxNP under PTAS reduction [KMS+99], [CT94].

Defined in [ACG+99].

---

AUC-SPACE(f(n)): Randomized Alternating f(n)-Space

The class of problems decidable by an O(f(n))-space Turing machine with three kinds of quantifiers: existential, universal, and randomized.

Contains GAN-SPACE(f(n)).

AUC-SPACE(poly(n)) = SAPTIME = PSPACE [Pap83].

[Con92] shows that AUC-SPACE(log n) has a natural complete problem, and is contained in NP ∩ coNP.

---

AuxPDA: Auxiliary Pushdown Automata

Equivalent to NAuxPDA^p without the running-time restriction.

Equals P [Coo71b].

---

AVBPP: Average-Case BPP

Defined in [OW93] to be the class of decision problems that have a good average-case BPP algorithm, whenever the input is chosen from an efficiently samplable distribution.

Note that this is not the same as the BPP version of AvgP.

---

AvgE: Average Exponential-Time With Linear Exponent

Has the same relation to E as AvgP does to P.

---

AvgP: Average Polynomial-Time

A distributional problem consists of a decision problem A, and a probability distribution μ over problem instances.

A function f, from strings to integers, is polynomial on μ-average if there exists a constant ε>0 such that the expectation of f^ε(x) is finite, when x is drawn from μ.

Then (A,μ) is in AvgP if there is an algorithm for A whose running time is polynomial on μ-average.

This convoluted definition is due to Levin [Lev86], who realized that simpler definitions lead to classes that fail to satisfy basic closure properties. Also see [Gol97] for more information.

If AvgP = DistNP then EXP = NEXP [BCG+92].

See also: (NP,P-samplable).

---

AW[P]: Alternating W[P]

Same as AW[SAT] but with 'circuit' instead of 'formula.'

Has the same relation to AW[SAT] as W[P] has to W[SAT].

Defined in [DF99].

---

AWPP: Almost WPP

The class of decision problems solvable by an NP machine such that for some polynomial-time computable (i.e. FP) function f,

1. If the answer is "no," then the difference between the number of accepting and rejecting paths is non-negative and at most 2^-poly(n)f(x).
2. If the answer is "yes," then the difference is between (1-2^-poly(n))f(x) and f(x).

Defined in [FFK94].

Contains BQP [FR98], WAPP [BGM02], LWPP, and WPP.

Contained in APP [Fen02].

---

AW[SAT]: Alternating W[SAT]

Basically has the same relation to W[SAT] as PSPACE does to NP.

The class of decision problems of the form (x,r,k₁,...,k_r) (r,k₁,...,k_r parameters), that are fixed-parameter reducible to the following problem, for some constant h:

Parameterized QBFSAT: Given a Boolean formula F (with no restriction on depth), over disjoint variable sets S₁,...,S_r. Does there exist an assignment to S₁ of Hamming weight k₁, such that for all assignments to S₂ of Hamming weight k₂, etc. (alternating 'there exists' and 'for all'), F is satisfied?

See W[1] for the definition of fixed-parameter reducibility.

Defined in [DF99].

Contains AW[*], and is contained in AW[P].

---

AW[*]: Alternating W[*]

The union of AW[t] over all t.

---

AW[t]: Alternating W[t]

Has the same relation to W[t] as PSPACE does to NP.

Same as AW[SAT], except that the formula F can have depth at most t.

Defined in [DF99].

Contained in AW[*].

---

AxP: Approximable in Polynomial Time

Usually called AP in the literature. I've renamed it AxP to distinguish it from the "other" AP.

The class of real-valued functions from {0,1}ⁿ to [0,1] that can be approximated within any ε>0 by a deterministic Turing machine in time polynomial in n and 1/ε.

Defined by [KRC00], who also showed that the set of AxP machines is in RE.

---

AxPP: Approximable in Probabilistic Polynomial Time

Usually called APP. I've renamed it AxPP to distinguish it from the "other" APP.

The class of real-valued functions from {0,1}ⁿ to [0,1] that can be approximated within any ε>0 by a probabilistic Turing machine in time polynomial in n and 1/ε.

Defined by [KRC00], who also show the following:

• Approximating the acceptance probability of a Boolean circuit is AxPP-complete. The authors argue that this makes AxPP a more natural class than BPP, since the latter is not believed to have complete problems.
• If AxPP = AxP, then BPP = P.
• On the other hand, there exists an oracle relative to which BPP = P but AxPP does not equal AxP.

Interestingly, it is unclear whether the set of AxPP machines is in RE.

---

βP: Limited-Nondeterminism NP

β_kP is the class of decision problems solvable by a polynomial-time Turing machine that makes O(log^kn) nondeterministic transitions, with the same acceptance mechanism as NP. Equivalently, the machine receives a purported proof of size O(log^kn) that the answer is 'yes.'

Then βP is the union of β_kP over all constant k.

Defined in [KF84]. See also the survey [GLM96].

There exist oracles relative to which basically any consistent inclusion structure among the β_kP's can be realized [BG98].

β₂P contains LOGNP and LOGSNP.

---

BH: Boolean Hierarchy Over NP

The smallest class that contains NP and is closed under union, intersection, and complement.

The levels are defined as follows:

• BH₁ = NP.
• BH_2i is the class of languages that are the intersection of a BH_2i-1 language with a coNP language.
• BH_2i+1 is the class of languages that are the union of a BH_2i language with an NP language.

Then BH is the union over all i of BH_i.

Defined in [WW85].

For more detail see [CGH+88].

Contained in Δ₂P and indeed in P^NP[log].

If BH collapses at any level, then PH collapses to Σ₃P [Kad88].

See also: QH.

---

BPE: Bounded-Error Probabilistic E

Has the same relation to E as BPP does to P.

EE = BPE if and only if EXP = BPP [IKW01].

---

BPEE: Bounded-Error Probabilistic EE

Has the same relation to EE as BPP does to P.

---

BP_HSPACE(f(n)): Bounded-Error Halting Probabilistic f(n)-Space

The class of decision problems solvable in O(f(n))-space with error probability at most 1/3, by a Turing machine that halts on every input and every random tape setting.

Contains R_HSPACE(f(n)).

Is contained in DSPACE(f(n)^3/2) [SZ95].

---

BPL: Bounded-Error Probabilistic L

Has the same relation to L as BPP does to P. The Turing machine has to halt with probability 1 on every input.

Contained in SC [Nis92] and in PL.

---

BP•NP: Probabilistic NP

Equals AM.

---

BPP: Bounded-Error Probabilistic Polynomial-Time

The class of decision problems solvable by an NP machine such that

1. If the answer is 'yes' then at least 2/3 of the computation paths accept.
2. If the answer is 'no' then at most 1/3 of the computation paths accept.

(Here all computation paths have the same length.)

Often identified as the class of feasible problems for a computer with access to a genuine random-number source.

Defined in [Gil77].

Contained in Σ₂P ∩ Π₂P [Lau83], and indeed in ZPP^NP [GZ97].

If BPP contains NP, then RP = NP [Ko82] and PH is contained in BPP [Zac88].

If any problem in E requires circuits of size 2^Ω(n), then BPP = P [IW97] (in other words, BPP can be derandomized).

Indeed, any proof that BPP = P requires showing either that NEXP is not in P/poly, or else that #P requires superpolynomial-size arithmetic circuits [KI02].

BPP is not known to contain complete problems. [Sip82], [HH86] give oracles relative to which BPP has no complete problems.

There exist oracles relative to which P = RP but still P is not equal to BPP [BF99].

In contrast to the case of P, it is unknown whether BPP collapses to BPTIME(n^c) for some fixed constant c. However, [Bar02] and [FS04] have shown hierarchy theorems for BPP with a small amount of advice.

See also: BPP_path.

---

BPP^cc: Communication Complexity BPP

The analogue of P^cc for bounded-error probabilistic communication complexity.

Does not equal P^cc, and is not contained in NP^cc, because of the EQUALITY problem.

Defined in [BFS86].

---

BPP^KT: BPP With Time-Bounded Kolmogorov Complexity Oracle

BPP with an oracle that, given a string x, returns the minimum over all programs P that output x_i on input i, of the length of P plus the maximum time taken by P on any input.

A similar class was defined in [ABK+02], where it was also shown that in BPP^KT one can factor, compute discrete logarithms, and more generally invert any one-way function on a non-negligible fraction of inputs.

See also: P^K.

---

BPP/log: BPP With Logarithmic Karp-Lipton Advice

The class of problems solvable by a semantic BPP machine with O(log n) advice bits that depend only on the input length n. If the advice is good, the output must be correct with probability at least 2/3. If it is bad, the machine must provide some answer with probability at least 2/3. See the discussion for BQP/poly.

Contained in BPP/mlog.

---

BPP/mlog: BPP With Logarithmic Deterministic Merlin-Like Advice

The class of problems solvable by a syntactic BPP machine with O(log n) advice bits that depend only on the input length n. If the advice is good, the output must be correct with probability at least 2/3. If it is bad, it need not be.

Contained in BPP/rlog.

---

BPP//log: BPP With Logarithmic Randomness-Dependent Advice

The class of problems solvable by a BPP machine that is given O(log n) advice bits, which can depend on both the machine's random coin flips and the input length n, but not on the input itself.

Defined in [TV02], where it was also shown that if EXP is in BPP//log then EXP = BPP, and if PSPACE is in BPP//log then PSPACE = BPP.

---

BPP/rlog: BPP With Logarithmic Deterministic Merlin-Like Advice

The class of problems solvable by a syntactic BPP machine with O(log n) random advice bits whose probability distribution depends only on the input length n. For each n, there exists good advice such that the output is correct with probability at least 2/3.

Contains BPP/mlog. The inclusion is strict, because BPP/rlog contains any finitely sparse language by fingerprinting; see the discussion for ALL.

Contained in BPP//log.

---

BPP-OBDD: Polynomial-Size Bounded-Error Ordered Binary Decision Diagram

Same as P-OBDD, except that probabilistic transitions are allowed and the OBDD need only accept with probability at least 2/3.

Does not contain the integer multiplication problem [AK96].

Strictly contained in BQP-OBDD [NHK00].

---

BPP_path: Threshold BPP

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:

• BPP_path contains MA and P^NP[log], and is contained in PP and BPP^NP.
• BPP_path is closed under complementation, intersection, and union.
• If BPP_path = BPP_path^BPPpath, then PH collapses to BPP_path.
• If BPP_path contains Σ₂P, then PH collapses to BPP^NP.

There exists an oracle relative to which BPP_path is not contained in Σ₂P [BGM02].

---

BPQP: Bounded-Error Probabilistic QP

Equals BPTIME(2^{O((log n)^k)}); that is, the class of problems solvable in quasipolynomial-time on a bounded-error machine.

Defined in [CNS99], where the following was also shown:

If either (1) #P does not have a subexponential-time bounded-error algorithm, or (2) EXP does not have subexponential-size circuits, then the BPQP hierarchy is strict -- that is, for all a < b at least 1, BPTIME(2^{(log n)^a}) is strictly contained in BPTIME(2^{(log n)^b}).

---

BPSPACE(f(n)): Bounded-Error Probabilistic f(n)-Space

The class of decision problems solvable in O(f(n))-space with error probability at most 1/3, by a Turing machine that halts with probability 1 on every input.

Contains RSPACE(f(n)) and BP_HSPACE(f(n)).

---

BPTIME(f(n)): Bounded-Error Probabilistic f(n)-Time

Same as BPP, but with f(n)-time (for some constructible function f) rather than polynomial-time machines.

Defined in [Gil77].

BPTIME(n^{log n}) does not equal BPTIME(2^{n^ε}) for any ε>0 [KV88]. Proving a stronger time hierarchy theorem for BPTIME is a longstanding open problem; see [BH97] for details.

[Bar02] has shown the following:

• If we allow a small number of advice bits (say log n), then there is a strict hierarchy: for every d at least 1, BPTIME(n^d)/(log n) does not equal BPTIME(n^d+1)/(log n).
• In the uniform setting, if BPP has complete problems then BPTIME(n^d) does not equal BPTIME(n^d+1).
• BPTIME(n) does not equal NP.

Subsequently, [FS04] managed to reduce the number of advice bits to only 1: BPTIME(n^d)/1 does not equal BPTIME(n^d+1)/1. They also proved a hierarchy theorem for HeurBPTIME.

For another bounded-error hierarchy result, see BPQP.

---

BQNC: Alternate Name for QNC

---

BQNP: Alternate Name for QMA

---

BQP: Bounded-Error Quantum Polynomial-Time

The class of decision problems solvable in polynomial time by a quantum Turing machine, with at most 1/3 probability of error.

One can equivalently define BQP as the class of decision problems solvable by a uniform family of polynomial-size quantum circuits, with at most 1/3 probability of error [Yao93]. Any universal gate set can be used as a basis; however, a technicality is that the transition amplitudes must be efficiently computable, since otherwise one could use them to encode the solutions to hard problems (see [ADH97]).

BQP is often identified as the class of feasible problems for quantum computers.

Contains the factoring and discrete logarithm problems [Sho97], the hidden Legendre symbol problem [DHI02], the Pell's equation and principal ideal problems [Hal02], and some other problems not thought to be in BPP.

Defined in [BV97], where it is also shown that BQP contains BPP and is contained in P with a #P oracle.

BQP^BQP = BQP [BV97].

[ADH97] showed that BQP is contained in PP, and [FR98] showed that BQP is contained in AWPP.

There exist oracles relative to which:

• BQP does not equal BPP [BV97] (and by similar arguments, is not in P/poly).
• BQP is not contained in MA [Wat00].
• BQP is not contained in Mod_pP for prime p [GV02].
• relative to a random oracle, with probability 1, NP (and indeed NP ∩ coNP) is not contained in BQP (i.e. BQP cannot solve NP problems using black-box approach, still there are no results about relation between NP and BQP) [BBB+97].
• SZK is not contained in BQP [Aar02].
• BQP is not contained in SZK (follows easily using the quantum walk problem in [CCD+03]).

---

BQP/log: BQP With Logarithmic-Size Karp-Lipton Advice

Same as BQP/poly except that the advice is O(log n) bits instead of a polynomial number.

Contained in BQP/mlog.

---

BQP/poly: BQP With Polynomial-Size Karp-Lipton Advice

Is to BQP/mpoly as ∃BPP is to MA. Namely, the BQP machine is required to give some answer with probability at least 2/3 even if the advice is bad. Even though BQP/mpoly is a more natural class, BQP/poly follows the standard definition of advice as a class operator [KL82].

Contained in BQP/mpoly and contains BQP/log.

---

BQP/mlog: BQP With Logarithmic-Size Deterministic Merlin-Like Advice

Same as BQP/mpoly except that the advice is O(log n) bits instead of a polynomial number.

Strictly contained in BQP/qlog [NY03].

---

BQP/mpoly: BQP With Polynomial-Size Deterministic Merlin-Like Advice

The class of languages recognized by a syntactic BQP machine with deterministic polynomial advice that depends only on the input length, such that the output is correct with probability 2/3 when the advice is good.

Can also be defined as the class of problems solvable by a nonuniform family of polynomial-size quantum circuits, just as P/poly is the class solvable by a nonuniform family of polynomial-size classical circuits.

Referred to with a variety of other ad hoc names, including BQP/poly on occassion.

Contains BQP/qlog, and is contained in BQP/qpoly.

Does not contain ESPACE [NY03].

---

BQP/qlog: BQP With Logarithmic-Size Quantum Advice

Same as BQP/mlog except that the advice is quantum instead of classical.

Strictly contains BQP/mlog [NY03].

Contained in BQP/mpoly.

---

BQP/qpoly: BQP With Polynomial-Size Quantum Advice

The class of problems solvable by a BQP machine that receives a quantum state ψ_n as advice, which depends only on the input length n.

As with BQP/mpoly, the acceptance probability does not need to be bounded away from 1/2 if the machine is given bad advice. (Thus, we are discussing the class that [NY03] call BQP/*Qpoly.) Indeed, such a condition would make quantum advice unusable, by a continuity argument.

Does not contain EESPACE [NY03].

[Aar04b] shows the following:

• There exists an oracle relative to which BQP/qpoly does not contain NP.
• BQP/qpoly is contained in PP/poly.

A classical oracle separation between BQP/qpoly and BQP/mpoly is presently unknown, but there is a quantum oracle separation [AK06]. An unrelativized separation is too much to hope for, since it would imply that PP is not contained in P/poly.

Contains BQP/mpoly.

---

BQP-OBDD: Polynomial-Size Bounded-Error Quantum Ordered Binary Decision Diagram

Same as P-OBDD, except that unitary (quantum) transitions are allowed and the OBDD need only accept with probability at least 2/3.

Strictly contains BPP-OBDD [NHK00].

---

BQPSPACE: Bounded-Error Quantum PSPACE

Equals PSPACE and PPSPACE.

---

BQTIME(f(n)): Bounded-Error Quantum f(n)-Time

Same as BQP, but with f(n)-time (for some constructible function f) rather than polynomial-time machines.

Defined in [BV97].

---

BQP_tt/poly: BQP/mpoly With Truth-Table Queries

Same as BQP/mpoly, except that the machine only gets to make nonadaptive queries to whatever oracle it might have.

Defined in [NY03b], where it was also shown that P is not contained in BQP_tt/poly relative to an oracle.

---

k-BWBP: Bounded-Width Branching Program

Alternate name for k-PBP.

---

C₌AC⁰: Exact-Counting AC⁰

The class of problems for which there exists a DiffAC⁰ function f such that the answer is "yes" on input x if and only if f(x)=0.

Equals TC⁰ and PAC⁰ under logspace uniformity [ABL98].

---

C₌L: Exact-Counting L

Has the same relation to L as C₌P does to P.

C₌L^C=L = L^C=L [ABO99].

---

C₌P: Exact-Counting Polynomial-Time

The class of decision problems solvable by an NP machine such that the number of accepting paths exactly equals the number of rejecting paths, if and only if the answer is 'yes.'

Equals coNQP [FGH+98].

---

CFL: Context-Free Languages

Does not equal QCFL [MC00].

Contained in LOGCFL.

Strictly contains DCFL [Bra77].

---

CH: Counting Hierarchy

The union of the C_kP's over all constant k.

Contained in PSPACE.

It is an open problem whether there exists an oracle relative to which CH is infinite, or even unequal to PSPACE. This is closely related to the problem of whether TC⁰ = NC¹.

---

Check: Checkable Languages

The class of problems such that a polynomial-time program P that allegedly solves them can be checked efficiently. That is, f is in Check if there exists a BPP algorithm C such that for all programs P and inputs x,

1. If P(y)=f(y) for all inputs y, then C^P(x) (C with oracle access to P) accepts with probability at least 2/3.
2. If P(x) is not equal to f(x) then C^P(x) accepts with probability at most 1/3.

Introduced in [BK89], where it was also shown that Check equals frIP ∩ cofrIP.

Check is contained in NEXP ∩ coNEXP [FRS88].

[BG94] show that if NEE is not contained in BPEE then NP is not contained in Check.

---

CL#P: Cluster Sharp-P

The class of #P function problems such that some underlying NP machine M witnessing membership in #P has "clustered" accepting paths. That is:

• There exists a polynomial p such that each computation path of M on each input x is exactly p( | x | ) bits long.
• There is a length-respecting total order A having polynomial-time computable adjacency checks on the computation paths of M.
• The accepting paths of M on any input x are contiguous with respect to A.

Defined in [HHK+05].

---

C_kP: k^th Level of CH

Defined as follows:

• C₀P = P
• C₁P = PP
• C₂P = PP^PP
• In general, C_k+1P is PP with C_kP oracle

The union of the C_kP's is called the counting hierarchy, CH.

Defined in [Wag86].

See [Tor91] or [AW90] for more information.

---

CLOG: Continuous Logarithmic-Time

Roughly, the class of continuous problems solvable by an ordinary differential equation (ODE) with convergence time logarithmic in the size of the input. The vector field of the ODE is specified by an NC¹ formula, with n parameters that represent the input. The point to which the ODE converges (assuming it does) is the output.

Defined in [BSF02], which should be consulted for more details.

[BSF02] show that finding the maximum of n integers is in CLOG. Thus, CLOG is best thought of as the continuous-time analog of NC¹, not of DTIME(log n).

Contained in CP.

---

CNP: Continuous NP

A nondeterministic analog of CP. Defined in [SF98], which should be consulted for the definition (it has something to do with strange attractors, I think).

The authors raise the question of whether CP equals CNP.

---

coAM: Complement of AM

---

coC₌P: Complement of C₌P

Equals NQP [FGH+98].

---

cofrIP: Complement of frIP

---

Coh: Coherent Languages

The class of problems L that are efficiently autoreducible, in the sense that given an input x and access to an oracle for L, a BPP machine can compute L(x) by querying L only on points that differ from x.

Defined in [Yao90b].

[BG94] show that, assuming NEE is not contained in BPEE, Coh ∩ NP is not contained in any of compNP, Check, or frIP.

---

coMA: Complement of MA

---

coMod_kP: Complement of Mod_kP

---

compIP: Competitive IP Proof System

Same as compNP but for interactive (IP) proofs instead of NP proofs.

More formally, compIP is the class of decision problems L in IP = PSPACE such that, if the answer is "yes," then that can be proven by an interactive protocol between a BPP verifier and a prover, a BPP machine with access only to an oracle for L.

Assuming NEE is not contained in BPEE, NP (and indeed NP ∩ Coh) is not contained in compIP [BG94].

---

compNP: Competitive NP Proof System

The class of decision problems L in NP such that, if the answer is "yes," then a proof can be constructed in polynomial time given access only to an oracle for L.

Contains NPC.

[BG94] show that compNP is contained in frIP, and that assuming NEE is not contained in BPEE, compNP does not equal NP.

---

coNE: Complement of NE

---

coNEXP: Complement of NEXP

Contained in NEXP/poly (folklore result reported in [weblog]).

---

coNL: Complement of NL

Equals NL [Imm88] [Sze87].

---

coNP: Complement of NP

If NP = coNP, then any inconsistent Boolean formula of size n has a proof of inconsistency of size polynomial in n.

If NP does not equal coNP, then P does not equal NP. But the other direction is not known.

See also: NP ∩ coNP.

Every problem in coNP has an IP (interactive proof) system, where moreover the prover can be restricted to BPP^#P.

---

coNP^cc: Complement of NP^cc

---

coNP/poly: Complement of NP/poly

If NP is contained in coNP/poly then PH collapses to S₂P^NP [CCH+01].

NPNP^NP^(coNP/poly ∩ NP) = NPNP^NP [HNO+96]

Note: At the suggestion of Luis Antuñes, the above specimen of the Complexity Zoo has been locked in a cage.

---

coNQP: Complement of NQP

Equals C₌P [FGH+98].

---

coRE: Complement of RE

Does not equal RE.

The problem "given a computable predicate P, is P true of all positive integers?" is coRE-complete.

---

coRNC: Complement of RNC

Contains the problem of whether a bipartite graph has a perfect matching [Kar86].

---

coRP: Complement of RP

Defined in [Gil77].

Contains the problem of testing whether an integer is prime [SS77].

---

coSL: Complement of SL

---

coSPARSE: Complement of SPARSE

---

coUCC: Complement of UCC

[Tor00] showed the following problem complete for coUCC under L reductions:

Given a colored graph G with at most two vertices having any given color, does G have any nontrivial automorphisms?

---

coUP: Complement of UP

---

CP: Continuous P

Same as CLOG, except that the convergence time can be polynomial rather than logarithmic in the input size.

Defined in [BSF02] and [SF98].

Finding a maximum flow, which is P-complete, can be done in CP [BSF02]. Based on this the authors argue that "P is contained in CP," but this seems hard to formalize, since CP is not a complexity class in the usual sense. They also conjecture that "CP is contained in P" (i.e. the class of ODE's they consider can be integrated efficiently on a standard Turing machine), but this is open.

Contained in CNP.

---

CSIZE(f(n)): Circuit Size f(n)

The class of decision problems solvable by a (nonuniform) family of Boolean circuits of size O(f(n)).

So for example, CSIZE(poly(n)) (the union of CSIZE(n^k) over all k) equals P/poly.

Defined in [SM02] among other places.

---

CSL: Context Sensitive Languages

The class of languages generated by context-sensitive grammars.

Equals NSPACE(n) [Kur64].

---

CZK: Computational Zero-Knowledge

Same as SZK, except that now the two distributions are merely required to be computationally indistinguishable by any BPP algorithm; they don't have to be statistically close. (The "two distributions" are (1) the distribution over Arthur's view of his interaction with Merlin, conditioned on Arthur's random coins, and (2) the distribution over views that Arthur can simulate without Merlin's help.)

Unlike SZK, it is not known if CZK is closed under complement. CZK is now known to share other properties with SZK: the verifier may as well be honest and may as well show his coins, and CZK is closed under unions [Vad06]. (Previously, these properties were only established in the presence of one-way functions.)

Assuming the existence of one-way functions, CZK contains NP [GMW91], and indeed equals IP=PSPACE [BGG+90]. However, none of these implications of one-way functions relativize (Impagliazzo, unpublished).

On the other hand, if one-way functions do not exist then CZK = AVBPP [OW93].

Contains PZK and SZK.

---

D#P: Alternate Name for P^#P

---

DCFL: Deterministic CFL

The class of languages accepted by deterministic pushdown automata.

Defined in [GG66], where it was also shown that DCFL is strictly contained in CFL and strictly contains REG.

---

Δ₂P: P With NP Oracle

A level of PH, the polynomial hierarchy.

Contains BH.

There exists an oracle relative to which Δ₂P is not contained in PP [Bei94].

There exists another oracle relative to which Δ₂P is contained in P/poly [BGS75], and indeed has linear-size circuits [Wil85].

If P = NP, then any polynomial-size circuit C can be learned in Δ₂P with C oracle [Aar06].

---

δ-BPP: δ-Semi-Random BPP

Same as BPP, except that the random bit source is biased as follows. Each bit could depend on all the previous bits in arbitrarily complicated ways; the only promise is that the bit is 1 with probability in the range [δ,1-δ], conditioned on all previous bits.

So clearly 0-BPP = P and 1/2-BPP = BPP.

It turns out that, for any δ>0, δ-BPP = BPP [VV85], [Zuc91].

---

δ-RP: δ-Semi-Random RP

Same as δ-BPP, but for RP instead of BPP.

For any δ>0, δ-RP = RP [VV85].

---

DET: Determinant

The class of decision problems reducible in L to the problem of computing the determinant of an n-by-n matrix of n-bit integers.

Defined in [Coo85].

Contained in NC², and contains NL and PL [BCP83].

Graph isomorphism is hard for DET under L-reductions [Tor00].

---

DiffAC⁰: Difference #AC⁰

The class of functions from {0,1}ⁿ to integers expressible as the difference of two #AC⁰ functions.

Equals GapAC⁰ under logspace uniformity [ABL98].

---

DisNP: Disjoint NP Pairs

The class of pairs (A,B), where A and B are NP problems whose sets of "yes" instances are nonempty and disjoint.

If there exists an optimal propositional proof system, then DisNP has a complete pair [Raz94]. On the other hand, there exists an oracle relative to which DisNP does not have a complete pair [GSS+03].

If P does not equal UP, then DisNP contains pairs not separated by any set in P [GS88]. On the other hand, there exists an oracle relative to which P does not equal NP but still DisNP does not contain any P-inseparable pairs [HS92].

---

DistNP: Distributional NP

(also called (NP,P-computable) or RNP)

A distributional problem consists of a decision problem A, and a probability distribution μ over problem instances.

(A,μ) is in DistNP if A is in NP, and μ is P-computable (meaning that its cumulative density function can be evaluated in polynomial time).

DistNP has complete problems [Gur87], although unlike for NP this is not immediate.

Any DistNP-complete problem is also complete for (NP,P-samplable) [IL90].

---

DP: Difference Polynomial-Time

DP = BH₂, the second level of the Boolean hierarchy.

Defined in [PY84].

---

DQP: Dynamical Quantum Polynomial-Time

The class of decision problems solvable by a BQP machine with oracle access to a dynamical simulator. When given a polynomial-size quantum circuit, the simulator returns a sample from the distribution over "classical histories" induced by the circuit. The simulator can adversarially choose any history distribution that satisfies the axioms of "symmetry" and "locality" -- so that the DQP algorithm has to work for any distribution satisfying these axioms.

See [Aar05] for a full definition.

There it is also shown that SZK is contained in DQP.

Contains BQP, and is contained in EXP [Aar05].

There exists an oracle relative to which DQP does not contain NP [Aar05].

---

DSPACE(f(n)): Deterministic f(n)-Space

The class of decision problems solvable by a Turing machine in space O(f(n)).

The Space Hierarchy Theorem: For constructible f(n) greater than log n, DSPACE(f(n)) is strictly contained in DSPACE(f(n) log(f(n))) [HLS65].

For space constructible f(n), strictly contains DTIME(f(n)) [HPV77].

DSPACE(n) does not equal NP (though we have no idea if one contains the other)!

See also: NSPACE(f(n)).

---

DTIME(f(n)): Deterministic f(n)-Time

The class of decision problems solvable by a Turing machine in time O(f(n)).

The Time Hierarchy Theorem: For constructible f(n) greater than n, DTIME(f(n)) is strictly contained in DTIME(f(n) log(f(n)) loglog(f(n))) [HS65].

For any space constructible f(n), DTIME(f(n)) is strictly contained in DSPACE(f(n)) [HPV77].

Also, DTIME(n) is strictly contained in NTIME(n) [PPS+83] (this result does not work for arbitrary f(n)).

For any constructible superpolynomial f(n), DTIME(f(n)) with PP oracle is not in P/poly (see [All96]).

---

DTISP(t(n),s(n)): Simultaneous t(n)-Time and s(n)-Space

The class of decision problems solvable by a Turing machine that uses time O(t(n)) and space O(s(n)) simultaneously.

Thus SC = DTISP(poly,polylog) for example.

Defined in [Nis92], where it was also shown that for all space-constructible s(n)=Ω(log n), BPSPACE(s(n)) is contained in DTISP(2^O(s(n)),s²(n)).

---

Dyn-FO: Dynamic FO

The class of dynamic problems solvable using first-order predicates.

Basically what this means is that an algorithm maintains some polynomial-size data structure (say a graph), and receives a sequence of updates (add this edge, delete that one, etc.). For each update, it computes a new value for the data structure in FO -- that is, for each bit of the data structure, there is an FO function representing the new value of that bit, which takes as input both the update and the previous value of the data structure. At the end the algorithm needs to answer some question (i.e. is the graph connected?).

See [HI02] for more information, and a complete problem for Dyn-FO.

See also Dyn-ThC⁰.

---

Dyn-ThC⁰: Dynamic Threshold Circuits

Same as Dyn-FO, except that now updates are computed via constant-depth predicates that have "COUNT" available, in addition to AND, OR, and NOT -- so it's a uniform version of TC⁰ rather than of AC⁰.

See [HI02] for more information.

---

E: Exponential Time With Linear Exponent

Equals DTIME(2^O(n)).

Does not equal NP [Boo72] or PSPACE [Boo74] relative to any oracle. However, there is an oracle relative to which E is contained in NP (see ZPP), and an oracle relative to PSPACE is contained in E (by equating the former with P).

There exists a problem that is complete for E under polynomial-time Turing reductions but not polynomial-time truth-table reductions [Wat87].

Problems hard for BPP under Turing reductions have measure 1 in E [AS94].

It follows that, if the problems complete for E under Turing reductions do not have measure 1 in E, then BPP does not equal EXP.

[IT89] gave an oracle relative to which E = NE but still there is an exponential-time binary predicate whose corresponding search problem is not in E.

Contrast with EXP.

---

EE: Double-Exponential Time With Linear Exponent

Equals DTIME(2^{2^O(n)}) (though some authors alternatively define it as being equal to DTIME(2^{O(2^n)})).

EE = BPE if and only if EXP = BPP [IKW01].

Contained in EEXP and NEE.

---

EEE: Triple-Exponential Time With Linear Exponent

Equals DTIME(2^{2^2^O(n)}).

In contrast to the case of EE, it is not known whether EEE = BPEE implies EE = BPE [IKW01].

---

EESPACE: Double-Exponential Space With Linear Exponent

Equals DSPACE(2^{2^O(n)}).

Is not contained in BQP/qpoly [NY03].

---

EEXP: Double-Exponential Time

Equals DTIME(2^{2^p(n)}) for p a polynomial.

Contains EE, and is contained in NEEXP.

---

EH: Exponential-Time Hierarchy With Linear Exponent

Has roughly the same relationship to E as PH does to P.

More formally, EH is defined as the union of E, NE, NE^NP, NE with Σ₂P oracle, and so on.

See [Har87] for more information.

If coNP is contained in AM[polylog], then EH collapses to S₂-EXP•P^NP [SS04] and indeed AM_EXP [PV04].

On the other hand, coNE is contained in NE/poly, so perhaps it wouldn't be so surprising if NE collapses.

There exists an oracle relative to which EH does not contain SEH [Hem89]. EH and SEH are incomparable for all anyone knows.

---

ELEMENTARY: Iterated Exponential Time

Equals the union of DTIME(2ⁿ), DTIME(2^{2^n}), DTIME(2^{2^2^n}), and so on.

Contained in PR.

---

EL_kP: Extended Low Hierarchy

An extension of L_kP.

The class of problems A such that Σ_kP^A is contained in Σ_k-1P^A,NP.

Defined in [BBS86].

---

EP: NP with 2^k Accepting Paths

The class of decision problems solvable by an NP machine such that

1. If the answer is 'no,' then all computation paths reject.
2. If the answer is 'yes,' then the number of accepting paths is a power of two.

Contained in C₌P, and in Mod_kP for any odd k. Contains UP.

Defined in [BHR00].

---

EPTAS: Efficient Polynomial-Time Approximation Scheme

The class of optimization problems such that, given an instance of length n, we can find a solution within a factor 1+ε of the optimum in time f(ε)p(n), where p is a polynomial and f is arbitrary.

Contains FPTAS and is contained in PTAS.

Defined in [CT97], where the following was also shown:

• If FPT = XP_uniform then EPTAS = PTAS.
• If EPTAS = PTAS then FPT = W[P].
• If FPT is strictly contained in W[1], then there is a natural problem that is in PTAS but not in EPTAS. (See [CT97] for the statement of the problem, since it's not that natural.)

---

k-EQBP: Width-k Polynomial-Time Exact Quantum Branching Programs

See k-PBP for the definition of a classical branching program.

A quantum branching program is the natural quantum generalization: we have a quantum state in a Hilbert space of dimension k. Each step t consists of applying a unitary matrix U^(t)(x_i): that is, U^(t) depends on a single bit x_i of the input. (So these are the quantum analogues of so-called oblivious branching programs.) In the end we measure to decide whether to accept; there must be zero probability of error.

Defined in [AMP02], where it was also shown that NC¹ is contained in 2-EQBP.

k-BQBP can be defined similarly.

---

EQP: Exact Quantum Polynomial-Time

The same as BQP, except that the quantum algorithm must return the correct answer with probability 1, and run in polynomial time with probability 1. Unlike bounded-error quantum computing, there is no theory of universal QTMs for exact quantum computing models. In the original definition in [BV97], each language in EQP is computed by a single QTM, equivalently to a uniform family of quantum circuits with a finite gate set K whose amplitudes can be computed in polynomial time. See EQP_K. However, some results require an infinite gate set. The official definition here is that the gate set should be finite.

Without loss of generality, the amplitudes in the gate set K are algebraic numbers [ADH97].

There is an oracle that separates EQP from NP [BV97], indeed from Δ₂P [GP01]. There is also an oracle relative to which EQP is not in Mod_pP where p is prime [GV02]. On the other hand, EQP is in LWPP [FR98].

P^||NP[2k] is contained in EQP^||NP[k], where "||NP[k]" denotes k nonadaptive oracle queries to NP (queries that cannot depend on the results of previous queries) [BD99].

See also ZBQP.

---

EQP_K: Exact Quantum Polynomial-Time with Gate Set K

The set of problems that can be answered by a uniform family of polynomial-sized quantum circuits whose gates are drawn from a set K, and that return the correct answer with probability 1, and run in polynomial time with probability 1, and the allowed gates are drawn from a set K. K may be either finite or countable and enumerated. If S is a ring, the union of EQP_K over all finite gate sets K whose amplitudes are in the ring R can be written EQP_S.

Defined in [ADH97] in the special case of a finite set of 1-qubit gates controlled by a second qubit. It was shown there that transcendental gates may be replaced by algebraic gates without decreasing the size of EQP_K.

[FR98] show that EQP_Q is in LWPP. The proof can be generalized to any finite, algebraic gate set K.

The hidden shift problem for a vector space over Z/2 is in EQP_Q by Simon's algorithm. The discrete logarithm problem over Z/p is in EQP_Q-bar using infinitely many gates [MZ03].

---

EQTIME(f(n)): Exact Quantum f(n)-Time

Same as EQP, but with f(n)-time (for some constructible function f) rather than polynomial-time machines.

Defined in [BV97].

---

ESPACE: Exponential Space With Linear Exponent

Equals DSPACE(2^O(n)).

If E = ESPACE then P = BPP [HY84].

Indeed if E has nonzero measure in ESPACE then P = BPP [Lut91].

ESPACE is not contained in P/poly [Kan82].

Is not contained in BQP/mpoly [NY03].

See also: EXPSPACE.

---

∃BPP: BPP With Existential Operator

The class of problems for which there exists a BPP machine M such that, for all inputs x,

• If the answer is "yes" then there exists a y such that M(x,y) accepts.
• If the answer is "no" then for all y, M(x,y) rejects.

Contains NP and BPP, and is contained in MA and SBP.

∃BPP seems obviously equal to MA, yet [FFK+93] constructed an oracle relative to which they're unequal! Here is the difference: if the answer is "yes," MA requires only that there exist a y such that for at least 2/3 of random strings r, M(x,y,r) accepts (where M is a P predicate). For all other y's, the proportion of r's such that M(x,y,r) accepts can be arbitrary (say, 1/2). For ∃BPP, by contrast, the probability that M(x,y) accepts must always be either at most 1/3 or at least 2/3, for all y's.

---

∃NISZK: NISZK With Existential Operator

Contains NP and NISZK, and is contained in the third level of PH.

---

EXP: Exponential Time

Equals the union of DTIME(2^p(n)) over all polynomials p.

Also equals P with E oracle.

If L = P then PSPACE = EXP.

If EXP is in P/poly then EXP = MA [BFL91].

Problems complete for EXP under many-one reductions have measure 0 in EXP [May94], [JL95].

There exist oracles relative to which

• EXP = NP = ZPP [Hel84],
• EXP = NEXP but still P does not equal NP [Dek76],
• EXP does not equal PSPACE [Dek76].

[BT04] show the following rather striking result: let A be many-one complete for EXP, and let S be any set in P of subexponential density. Then A-S is Turing-complete for EXP.

---

EXP/poly: Exponential Time With Polynomial-Size Advice

The class of decision problems solvable in EXP with the help of a polynomial-length advice string that depends only on the input length.

Contains BQP/qpoly [Aar04b].

---

EXPSPACE: Exponential Space

Equals the union of DSPACE(2^p(n)) over all polynomials p.

See also: ESPACE.

Given a first-order statement about real numbers, involving only addition and comparison (no multiplication), we can decide in EXPSPACE whether it's true or not [Ber80].

---

FBQP: Function BQP

Has the same relation to BQP as FNP does to NP.

There exists an oracle relative to which PLS is not contained in FBQP [Aar03].

---

Few: FewP With Flexible Acceptance Mechanism

The class of decision problems solvable by an NP machine such that

1. The number of accepting paths a is bounded by a polynomial in the size of the input x.
2. For some polynomial-time predicate Q, Q(x,a) is true if and only if the answer is 'yes.'

Also called FewPaths.

Defined in [CH89].

Contains FewP, and is contained in P^FewP [Kob89] and in SPP [FFK94].

See also the survey [Tor90].

---

FewP: NP With Few Witnesses

The class of decision problems solvable by an NP machine such that

1. If the answer is 'no,' then all computation paths reject.
2. If the answer is 'yes,' then at least one path accepts; furthermore, the number of accepting paths is upper-bounded by a polynomial in n, the size of the input.

Defined in [AR88].

Is contained in ⊕P [CH89].

There exists an oracle relative to which P, UP, FewP, and NP are all distinct [Rub88].

Also, there exists an oracle relative to which FewP does not have a Turing-complete set [HJV93].

Contained in Few.

See also the survey [Tor90].

---

FH: Fourier Hierarchy

FH_k is the class of problems solvable by a uniform family of polynomial-size quantum circuits, with k levels of Hadamard gates and all other gates preserving the computational basis. (Conditional phase flip gates are fine, for example.) Thus

• FH₀ = P
• FH₁ = BPP
• FH₂ contains factoring, because of Kitaev's phase estimation algorithm

It is an open problem to show that the Fourier hierarchy is infinite relative to an oracle (that is, FH_k is strictly contained in FH_k+1).

Defined in [Shi03].

---

FNL: Function NL

Has the same relation to NL as FNP does to NP.

Defined by [AJ93], who also showed that if NL = UL, then FNL is contained in #L.

---

FNL/poly: Nonuniform FNL

Has the same relation to FNL as P/poly does to P.

Contained in #L/poly [RA00].

---

FNP: Function NP

The class of function problems of the following form:

Given an input x and a polynomial-time predicate F(x,y), if there exists a y satisfying F(x,y) then output any such y, otherwise output 'no.'

FNP generalizes NP, which is defined in terms of decision problems only.

Actually the word "function" is misleading, since there could be many valid outputs y. That's unavoidable, since given a predicate F there's no "syntactic" criterion ensuring that y is unique.

FP = FNP if and only if P = NP.

Contains TFNP.

A basic question about FNP problems is whether they're self-reducible; that is, whether they reduce to the corresponding NP decision problems. Although this is true for all NPC problems, [BG94] shows that if EE does not equal NEE, then there is a problem in NP such that no corresponding FNP problem can be reduced to it. [BG94] cites Impagliazzo and Sudan as giving the same conclusion under the assumption that NE does not equal coNE.

---

FO(t(n)): First-Order

The class of decision problems for which a "yes" answer can be expressed by a first-order logic predicate, with a block of restricted quantifiers repeated t(n) times. See [Imm98] for a full definition.

FO(poly(n)) = P (see [Var82] for example).

FO(poly(n)) is contained in SO-E.

---

FOLL: First-Order loglog n

The class of decision problems solvable by a nonuniform family of polynomial-size, unbounded-fanin, depth O(loglog n) circuits with AND, OR, and NOT gates.

Defined in [BKL+00], where it was also shown that many problems on finite groups are in FOLL.

Contains AC⁰, and is contained in AC¹.

Is not known to be comparable to L/poly or NL/poly.

---

FP: Function Polynomial-Time

Sometimes defined as the class of functions computable in polynomial time by a Turing machine. (Generalizes P, which is defined in terms of decision problems only.)

However, if we want to compare FP to FNP, we should instead define it as the class of FNP problems (that is, polynomial-time predicates P(x,y)) for which there exists a polynomial-time algorithm that, given x, outputs any y such that P(x,y). That is, there could be more than one valid output, even though any given algorithm only returns one of them.

FP = FNP if and only if P = NP.

If FP^NP = FP^NP[log] (that is, allowed only a logarithmic number of queries), then P = NP [Kre88]. The corresponding result for P^NP versus P^NP[log] is not known, and indeed fails relative to some oracles (see [Har87b]).

---

FP^NP[log]: FP With Logarithmically Many Queries To NP

Given a graph, the problem of outputting the size of its maximum clique is complete for FP^NP[log].

---

FPR: Fixed-Parameter Randomized

Has the same relation to FPT as R does to P.

Defined in [AR01], where it was shown that, if the Resolution proof system is automatizable (that is, if a refutation can always be found in time polynomial in the length of the shortest refutation), then W[P] is contained in FPR.

---

FPRAS: Fully Polynomial Randomized Approximation Scheme

The subclass of #P counting problems whose answer, y, is approximable in the following sense. There exists a randomized algorithm that, with probability at least 1-δ, approximates y to within an ε multiplicative factor in time polynomial in n (the input size), 1/ε, and log(1/δ).

The permanent of a nonnegative matrix is in FPRAS [JSV01].

---

FPT: Fixed-Parameter Tractable

The class of decision problems of the form (x,k), k a parameter, that are solvable in time f(k)p(|x|), where f is arbitrary and p is a polynomial.

The basic class of the theory of fixed-parameter tractability, as described by Downey and Fellows [DF99].

Contained in FPT_nu, W[1], and FPR.

Contains FPTAS [CC97], as well as FPT_su.

Contains PTAS unless FPT = W[1] [Baz95].

---

FPT_nu: Fixed-Parameter Tractable (nonuniform)

Same as FPT except that the algorithm can vary with the parameter k (though its running time must always be O(p(|x|)), for a fixed polynomial p).

An alternate view is that a single algorithm can take a polynomial-length advice string, depending on k.

Defined in [DF99] (though they did not use our notation).

---

FPT_su: Fixed-Parameter Tractable (strongly uniform)

Same as FPT except that f has to be recursive.

Defined in [DF99] (though they did not use our notation).

---

FPTAS: Fully Polynomial-Time Approximation Scheme

The subclass of NPO problems that admit an approximation scheme in the following sense. For any ε>0, there is an algorithm that is guaranteed to find a solution whose cost is within a 1+ε factor of the optimum cost. Furthermore, the running time of the algorithm is polynomial in n (the size of the problem) and in 1/ε.

Contained in PTAS.

Defined in [ACG+99].

Contained in FPT [CC97].

---

FQMA: Function QMA

The class of problems for which the task is to output a quantum certificate for a QMA problem, when such a certificate exists. Thus, the desired output is a quantum state.

Defined in [JWB03], where it is also shown that state preparation for 3-local Hamiltonians is FQMA-complete. The authors also observe that, in contrast to the case of FNP versus NP, there is no obvious reduction of FQMA problems to QMA problems.

---

frIP: Function-Restricted IP Proof Systems

The class of problems L that have a decider in the following sense. There exists a BPP machine D such that for all inputs x,

1. If the answer is "yes" then D^L(x) (D with oracle for L) accepts with probability at least 2/3.
2. If the answer is "no" then D^A(x) accepts with probability at most 1/3 for all oracles A.

Contains compIP [BG94] and Check [BK89].

Contained in MIP = NEXP [FRS88].

Assuming NEE is not contained in BPEE, NP (and indeed NP ∩ Coh) is not contained in frIP [BG94].

---

F-TAPE(f(n)): Provable DSPACE(f(n)) For Formal System F

The class of decision problems that can be proven to be solvable in O(f(n)) space on a deterministic Turing machine, from the axioms of formal system F.

Defined in [Har78].

See also F-TIME(f(n)). The results about F-TAPE mirror those about F-TIME, but in some cases are sharper.

---

F-TIME(f(n)): Provable DTIME(f(n)) For Formal System F

The class of decision problems that can be proven to be solvable in O(f(n)) time on a deterministic Turing machine, from the axioms of formal system F.

Defined in [Har78], where the following was also shown:

• If F-TIME(f(n)) = DTIME(f(n)), then DTIME(f(n)) is strictly contained in DTIME(f(n)g(n)) for any nondecreasing, unbounded, recursive g(n).
• There exist recursive, monotonically increasing f(n) such that F-TIME(f(n)) is strictly contained in DTIME(f(n)).

See also F-TAPE(f(n)).

---

GA: Graph Automorphism

Can be defined as the class of problems polynomial-time Turing reducible to the problem of deciding whether a given graph has any nontrivial automorphisms.

Contains P and is contained in GI.

See [KST93] for much more information about GA.

---

GAN-SPACE(f(n)): Games Against Nature f(n)-Space

The class of problems decidable by an O(f(n))-space Turing machine with two kinds of quantifiers: existential and randomized.

Contains NSPACE(f(n)) and BPSPACE(f(n)), and is contained in AUC-SPACE(f(n)).

By linear programming, GAN-SPACE(log n) is contained in P.

---

GapAC⁰: Gap #AC⁰

The class of functions from {0,1}ⁿ to integers computable by constant-depth, polynomial-size arithmetic circuits with addition and multiplication gates and the constants 0, 1, and -1. (The only difference from #AC⁰ is the ability to subtract, using the constant -1.)

Equals DiffAC⁰ under logspace uniformity [ABL98].

---

GapL: Gap Logarithmic-Space

Has the same relation to L as GapP does to P.

---

GapP: Gap Polynomial-Time

The class of functions f(x) such that for some NP machine, f(x) is the number of accepting paths minus the number of rejecting paths.

Equivalently, the closure of the #P functions under subtraction.

Defined in [FFK94] and independently [Gup95].

---

GC(s(n),C): Guess and Check

The class of decision problems for which a "yes" answer can be verified by

1. guessing s(n) bits, then
2. verifying the answer in complexity class C.

For example, GC(p(n),P) = NP where p is a polynomial.

Defined in [CC93].

Umans [Uma98] has shown that given a DNF expression Φ, the Shortest Implicant problem (is there a conjunction of at most k negated or non-negated literals that implies Φ?) is GC(log²n, coNP)-complete.

---

GCSL: Growing CSL

The class of languages generated by context-sensitive grammars in which the right-hand side of each transformation is strictly longer than the left-hand side.

Defined in [DW86].

---

GI: Graph Isomorphism

Can be defined as the class of problems polynomial-time Turing reducible to the problem of deciding whether two graphs are isomorphic.

Contains GA and is contained in Δ₂P.

The GI problem itself (as opposed to the set of problems Turing reducible to GI) is contained in NP as well as coAM (and indeed SZK). So in particular, if graph isomorphism is NP-complete, then PH collapses.

See [KST93] for much more information about GI.

---

GLO: Guaranteed Local Optima

The class of NPO problems which have the property that for all locally optimal solutions, the ratio between the values of the local and global optima is upper-bounded by a constant.

Defined in [AP95], where it was also shown that GLO is strictly contained in APX.

[KMS+99] showed that MaxSNP is not contained in GLO.

---

GPCD(r(n),q(n)): Generalized Probabilistically Checkable Debate

Same as PCD(r(n),q(n)), except that now the verifier is allowed nonadaptively to query O(q(n)) rounds of the debate, with no restriction on the number of bits it looks at within each round.

Defined in [CFL+93], who also showed that PCD(log n, q(n)) = GPCD(log n, q(n)) for every q(n).

---

G[t]: Stratification of Fixed-Parameter Tractable Problems

(Basically) the class of decision problems of the form (x,k) (k a parameter), that are solvable by a parameterized family of circuits with unbounded fanin and depth t. A uniformity condition may also be imposed.

Defined in [DF99], which should be consulted for the full definition.

Uniform G[P] (i.e. with no restriction on depth) is equal to FPT.

---

HalfP: RP With Exactly Half Acceptance

The class of decision problems solvable by an NP machine such that

1. If the answer is 'yes,' exactly 1/2 of computation paths accept.
2. If the answer is 'no,' all computation paths reject.

Significantly, the number of candidate witnesses is restricted to be a power of 2. (This is implicit if they are binary strings.)

Contained in RP, EP, and Mod_kP for every odd k. Contained in EQP by the Deutsch-Jozsa algorithm.

Defined in [BB92], where it was called C₌₌P[half]. The name used here is from [BS00]. There it was shown that HalfP is contained in every similar class in which 1/2 is replaced by some other dyadic fraction.

---

HeurBPP: Heuristic BPP

The class of problems for which a 1-1/poly(n) fraction of instances are solvable by a BPP machine.

[FS04] showed a strict hierarchy theorem for HeurBPP; thus, HeurBPP does not equal HeurBPTIME(n^c) for any fixed c.

---

HeurBPTIME(f(n)): Heuristic BPTIME(f(n))

The class of problems for which a 1-1/poly(n) fraction of instances are solvable by a BPTIME(f(n)) machine.

Thus HeurBPP is the union of HeurBPTIME(n^c) over all c.

---

H_kP: High Hierarchy In NP

The class of problems A in NP such that Σ_kP^A = Σ_k+1P; that is, adding A as an oracle increases the power of the k^th level of the polynomial hierarchy by a maximum amount.

For all k, H_k is contained in H_k+1.

Defined in [Sch83].

See also L_kP.

---

HVSZK: Honest-Verifier SZK

The class of decision problems that have SZK protocols assuming an honest verifier (i.e. one who doesn't try to learn more about the problem by deviating from the protocol).

Equals SZK [Oka96].

---

IC[log,poly]: Logarithmic Instance Complexity, Polynomial Time

The class of decision problems such that, for every n-bit string x, there exists a program A of size O(log n) that, given x as input, "correctly decides" the answer on x in time polynomial in n. This means:

• There exists a polynomial p such that for any input y, A returns either "yes", "no", or "I don't know" in time p(|y|).
• Whenever A returns "yes" or "no", it is correct.
• A returns either "yes" or "no" on x.

Defined in [OKS+94]; see also [LV97].

If NP is contained in IC[log,poly], then P = NP [OKS+94]. Indeed, any self-reducible problem in IC[log,poly] is also in P.

Strictly contains P/log, and is strictly contained in P/poly.

---

IP: Interactive Proof

The class of decision problems for which a "yes" answer can be verified by an interactive proof. Here a BPP (i.e. probabilistic polynomial-time) verifier sends messages back and forth with an all-powerful prover. They can have polynomially many rounds of interaction. Given the verifier's algorithm, at the end:

1. If the answer is "yes," the prover must be able to behave in such a way that the verifier accepts with probability at least 2/3 (over the choice of the verifier's random bits).
2. If the answer is "no," then however the prover behaves the verifier must reject with probability at least 2/3.

IP contains PH [LFK+90], and indeed (this was discovered only a few days later) equals PSPACE [Sha90]. On the other hand, coNP is not contained in IP relative to a random oracle [CCG+94].

See also: MIP, QIP, MA, AM.

---

IPP: Unbounded IP

Same as IP, except that if the answer is "yes," there need only be a prover strategy that causes the verifier to accept with probability greater than 1/2, while if the answer is "no," then for all prover strategies the verifier accepts with probability less than 1/2.

Defined in [CCG+94], where it was also shown that IPP = PSPACE relative to all oracles. Since IP is strictly contained in PSPACE relative to a random oracle, the authors interpreted this as evidence against the Random Oracle Hypothesis (a slight change in definition can cause the behavior of a class relative to a random oracle to change drastically).

See also: PPSPACE.

---

IP[polylog]: Alternate Name for AM[polylog]

---

L: Logarithmic Space

The class of decision problems solvable by a Turing machine restricted to use an amount of memory logarithmic in the size of the input, n. (The input itself is not counted as part of the memory.)

L contains NC¹ [Bor77], and is contained in generalizations including NL, L/poly, SL, RL, ⊕L, and Mod_kL.

Reingold [Rei04] showed that, remarkably, L = SL. In other words, undirected graph connectivity is solvable in deterministic logarithmic space.

---

LIN: Linear Time

The class of decision problems solvable by a deterministic Turing machine in linear time.

Contained in NLIN.

---

L_kP: Low Hierarchy In NP

The class of problems A such that Σ_kP^A = Σ_kP; that is, adding A as an oracle does not increase the power of the k^th level of the polynomial hierarchy.

L₁P = NP ∩ coNP.

For all k, L_k is contained in L_k+1 and in NP.

Defined in [Sch83].

See also H_kP.

---

LOGCFL: Logarithmically Reducible to CFL

The class of decision problems reducible in L to the problem of deciding membership in a context-free language.

Equivalently, LOGCFL is the class of decision problems solvable by a uniform family of AC¹ circuits, in which no AND gate has fan-in exceeding 2 (see e.g. [Joh90], p. 137).

LOGCFL is closed under complement [BCD+89].

Contains NL [Sud78].

---

LogFew: Logspace-Bounded Few

The class of decision problems solvable by an NL machine such that

1. The number of accepting paths on input x is f(x), and
2. The answer is 'yes' if and only if R(x,f(x))=1, where R is some predicate computable in L.

Defined in [BDH+92], where it was also shown that LogFew is contained in Mod_kL for all k>1.

---

LogFewNL: Logspace-Bounded FewP

Same as FewP but for logspace-bounded (i.e. NL) machines.

Defined in [BDH+92], where it was also shown that LogFewNL is contained in ModZ_kL for all k>1.

---

LOGNP: Logarithmically-Restricted NP

The class of decision problems expressible in logical form as

The set of I for which there exists a subset S={s₁,...,s_{log n}} of {1,...,n} of size log n, such that for all x there exists y such that for all j, the predicate φ(I,s_j,x,y,j) holds. Here x and y are logarithmic-length strings, or equivalently polynomially bounded numbers, and φ is computable in P.

LOGNP₀ is the subclass in which φ is a first-order predicate without quantifiers and x and y are bounded lists of indices of input bits. LOGNP is also the closure of LOGNP₀ under many-one reduction.

The motivation is that the analogue of LOGNP₀ without the logarithmic bound on |S| is SO-E, which by Fagin's theorem equals NP [Fag74].

Defined in [PY96], where it was also shown that the following problem is complete for LOGNP under many-one reductions:

Vapnik-Chernonenkis (V-C) Dimension. Given a family F of subsets of a set U, find a subset of S of U of maximum cardinality, such that every subset of S can be written as the intersection of S with some set in F.

Contains LOGSNP, and is contained in βP (indeed β₂P).

---

LOGSNP: Logarithmically-Restricted SNP

The class of decision problems expressible in logical form as

The set of I for which there exists a subset S={s₁,...,s_{log n}} of {1,...,n} of size log n, such that for all x there exists j such that the predicate φ(I,s_j,x,j) holds. Here x and y are logarithmic-length strings, or equivalently polynomially bounded numbers, and φ is computable in P.

LOGSNP₀ is the subclass in which φ is a first-order predicate without quantifiers and x is a bounded lists of indices of input bits. LOGSNP is also the closure of LOGSNP₀ under many-one reduction. See LOGNP and SNP for the motivation.

Defined in [PY96].

Contained in LOGNP, and therefore QPLIN.

If P = LOGSNP, then for every constructible f(n) > n, NTIME(f(n)) is contained in DTIME(g(n)^sqrt(g(n))), where g(n) = O(f(n) logf(n)) [FK97].

---

L/poly: Nonuniform Logarithmic Space

Has the same relation to L as P/poly does to P.

Equals PBP [Cob66].

Contains SL [AKL+79].

---

LWPP: Length-Dependent Wide PP

The class of decision problems solvable by an NP machine such that

1. If the answer is "no," then the number of accepting computation paths exactly equals the number of rejecting paths.
2. If the answer is "yes," then the difference of these numbers equals a function f(|x|) computable in polynomial time (i.e. FP). Here |x| is the length of the input x, and ``polynomial time means polynomial in |x|, the length of x, rather than the length of |x|.

Defined in [FFK94], where it was also shown that LWPP is low for PP and C₌P. (I.e. adding LWPP as an oracle does not increase the power of these classes.)

Contained in WPP and AWPP.

Contains SPP.

Also, contains the graph isomorphism problem [KST92].

Contains a whole litter of problems for solvable black-box groups: group intersection, group factorization, coset intersection, and double-coset membership [Vin04]

---

MA: Merlin-Arthur

The class of decision problems solvable by a Merlin-Arthur protocol, which goes as follows. Merlin, who has unbounded computational resources, sends Arthur a polynomial-size purported proof that the answer to the problem is "yes." Arthur must verify the proof in BPP (i.e. probabilistic polynomial-time), so that

1. If the answer is "yes," then there exists a proof such that Arthur accepts with probability at least 2/3.
2. If the answer is "no," then for all proofs Arthur accepts with probability at most 1/3.

An alternative definition requires that if the answer is "yes," then there exists a proof such that Arthur accepts with certainty. However, the definitions with one-sided and two-sided error can be shown to be equivalent (exercise for the Zoo visitor).

Contains NP and ∃BPP, and is contained in AM and in QMA.

Also contained in Σ₂P ∩ Π₂P.

There exists an oracle relative to which BQP is not in MA [Wat00].

Equals NP under a derandomization assumption.

See also: MA_E, MA_EXP.

---

MA': Sparse MA

The subclass of MA such that for each input size n, there is a sparse set S_n that Merlin's proof string always belongs to (no matter what the input is).

Defined in [KST93], where it is also observed that if graph isomorphism is in P/poly, then the complement of graph isomorphism is in MA'.

---

MAC⁰: Majority of AC⁰

Same as AC⁰, except now we're allowed a single unbounded-fanin majority gate at the root.

Defined in [JKS02].

MAC⁰ is strictly contained in TC⁰ [ABF+94].

---

MA_E: Exponential-Time MA With Linear Exponent

Same as MA, except now Arthur is E instead of polynomial-time.

If MA_E = NEE then MA = NEXP ∩ coNEXP [IKW01].

---

MA_EXP: Exponential-Time MA

Same as MA, except now Arthur is EXP instead of polynomial-time, and the message from Merlin can be exponentially long.

There is a problem in MA_EXP that does not have polynomial-size circuits [BFT98]. On the other hand, there is an oracle relative to which every problem in MA_EXP does have polynomial-size circuits.

[MVW99] considered the best circuit lower bound obtainable for a problem in MA_EXP, using current techniques. They found that this bound is half-exponential: i.e. a function f such that f(f(n))=2ⁿ. Such functions exist, but are not expressible using standard asymptotic notation.

---

mAL: Monotone AL

Defined in [GS90]. Equals mP by definition.

---

MaxNP: Maximization NP

Has the same relation to NP as MaxSNP does to SNP.

Contains MaxPB.

The closure of MaxNP under PTAS reduction is APX [KMS+99], [CT94].

---

MaxPB: MaxNP Polynomially Bounded

The subclass of MaxNP problems for which the cost function is guaranteed always to be bounded by a polynomial.

MinPB can be defined similarly.

Defined in [KT94].

The closure of MaxPB under PTAS reductions equals NPOPB [CKS+99].

---

MaxSNP: Maximization SNP

The class of optimization problems reducible by an "L-reduction" to a problem in MaxSNP₀. (Note: 'L' stands for linear -- this is not the same as an L reduction! For more details see [PY88].)

Defined in [PY88], where the following was also shown:

• Max3SAT is MaxSNP-complete. (Max3SAT is the problem of finding an assignment that maximizes the number of satisfied clauses in a CNF formula with at most 3 literals per clause.)
• Any problem in MaxSNP can be approximated to within a fixed ratio.

The closure of MaxSNP under PTAS reduction is APX [KMS+99], [CT94].

---

MaxSNP₀: Generating Class of MaxSNP

The class of function problems expressible as "find a relation such that the set of k-tuples for which a given SNP predicate holds has maximum cardinality."

For example (see [Pap94]), the Max-Cut problem can be expressed as follows:

Given a graph G, find a subset S of vertices that maximizes the number of pairs (u,v) of vertices such that u is in S, and v is not in S, and G has an edge from u to v.

Defined in [PY88].

---

mcoNL: Complement of mNL

Defined in [GS90], where it was also shown that mcoNL does not equal mNL.

See also: mL.

---

MinPB: MinNP Polynomially Bounded

Same as MaxPB but for minimization instead of maximization problems.

---

MIP: Multi-Prover Interactive Proof

Same as IP, except that now the verifier can exchange messages with many provers, not just one. The provers cannot communicate with each other during the execution of the protocol, so the verifier can "cross-check" their assertions (as with suspects in separate interrogation rooms).

Defined in [BGK+88].

Let MIP[k] be the class of decision problems for which a "yes" answer can be verified with k provers. Then for all k>2, MIP[k] = MIP[2] = MIP [BGK+88].

MIP equals NEXP [BFL91]; this is a famous non-relativizing result.

---

MIP*[2,1]: 2-Prover, 1-Round MIP With Quantum Provers

Same as MIP[2], except that now only one round is allowed, and the two provers can share arbitrarily many entangled qubits. The verifier is classical, as are all messages between the provers and verifier.

Defined in [CHT+04], where evidence was given suggesting that MIP* does not "obviously" equal NEXP. By contrast, MIP[2,1], the corresponding class without entanglement, equals NEXP.

Indeed, the relationship between MIP* and MIP = NEXP is completely unknown -- either could contain the other, or they could be incomparable.

It is also unknown whether increasing the number of provers or rounds changes MIP*[2,1].

Contains XOR-MIP*[2,1].

---

MIP_EXP: Exponential-Time Multi-Prover Interactive Proof

The exponential-time analogue of MIP.

In the unrelativized world, equals NEEXP.

There exists an oracle relative to which MIP_EXP equals the intersection of P/poly, P^NP, and ⊕P [BFT98].

---

(M_k)P: Acceptance Mechanism by Monoid M_k

A monoid is a set with an associative operation and an identity element (so it's like a group, except that it need not have inverses).

Then (M_k)P is the class of decision problems solvable by an NP machine with the following acceptance mechanism. The i^th computation path (under some lexicographic ordering) outputs an element m_i of M_k. Then the machine accepts if and only if m₁m₂...m_s is the identity (where s is the number of paths).

Defined by Hertrampf [Her97], who also showed the following (in the special case M is a group):

• If G is any nonsolvable group (for example S₅, the symmetric group on 5 elements), then (G)P = PSPACE.
• (Z_k)P = coMod_kP, where Z_k is the cyclic group on k elements.
• If |G|=k, then (G)P contains coMod_kP.

---

mL: Monotone L

The class of decision problems solvable by a family of monotone log-width polynomial-size leveled circuits. (A leveled circuit is one where gates on each level can depend only on the level immediately below it.)

Defined in [GS90], who raise as an open problem to define a uniform version of mL.

Strictly contains mNC¹ [GS91].

Contained in (nonuniform versions of) mNL and mcoNL.

---

mNC¹: Monotone NC¹

The class of decision problems solvable by a family of monotone NC¹ circuits (i.e. AND and OR gates only).

A uniformity condition could also be imposed.

Defined in [GS90].

Strictly contained in mNL [KW88], and indeed in mL [GS91].

Strictly contains mTC⁰ [Yao89].

---

mNL: Monotone NL

See mP for the definition of a monotone nondeterministic Turing machine, due to [GS90].

mNL is the class of decision problems solvable by a monotone nondeterministic log-space Turing machine.

mNL does not equal mcoNL [GS90], in contrast to the case for NL and coNL.

Also, mNL strictly contains mNC¹ [KW88].

See also: mL.

---

mNP: Monotone NP

The class of decision problems for which a 'yes' answer can be verified in mP (that is, monotone polynomial-time). The monotonicity requirement applies only to the input bits, not to the bits that are guessed nondeterministically. So, in the corresponding circuit, one can have NOT gates so long as they depend only on the nondeterministic guess bits.

Defined in [GS90], where it was also shown that mNP is 'trivial': that is, it contains exactly the monotone problems in NP.

Strictly contains mP [Raz85].

---

Mod_kL: Mod-k L

Has the same relation to L as Mod_kP does to P.

For any prime k, Mod_kL contains SL [KW93].

For any prime k, Mod_kL^ModkL = Mod_kL [HRV00].

For any k>1, contains LogFew [BDH+92].

---

Mod_kP: Mod-k Polynomial-Time

For any k>1: The class of decision problems solvable by an NP machine such that the number of accepting paths is divisible by k, if and only if the answer is "no."

Mod₂P is more commonly known as ⊕P "parity-P."

For every k, Mod_kP contains graph isomorphism [AK02].

Defined in [CH89], [Her90].

[Her90] and [BG92] showed that Mod_kP is the set of unions of languages in Mod_pP for each prime p that divides k. In particular, if p is prime, then Mod_pP = Mod_p^mP for all positive integers m. A further fact is that Mod_pP is closed under union, intersection, and complement for p prime.

On the other hand, if k is not a prime power, then there exists an oracle relative to which Mod_kP is not closed under intersection or complement [BBR94].

For prime p, there exists an oracle relative to which Mod_pP does not contain EQP [GV02].

---

ModP: Mod_kP With Arbitrary k

The class of decision problems solvable by a Mod_kP machine where k can vary depending on the input. The only requirement is that 0^k be computable in polynomial time.

Defined in [KT96], where it was also shown that ModP is contained in AmpMP.

---

ModZ_kL: Restricted Mod_kL

The class of decision problems solvable by a nondeterministic logspace Turing machine, such that

1. If the answer is "yes," then the number of accepting paths is not congruent to 0 mod k.
2. If the answer is "no," then there are no accepting paths.

Defined in [BDH+92], where it was also shown that ModZ_kL contains LogFewNL for all k>1.

Contained in Mod_kL and in NL.

---

mP: Monotone P

The definition of this class, due to [GS90], is not obvious. First, a monotone nondeterministic Turing machine is one such that, whenever it can make a transition with a 0 on its input tape, it can also make that same transition with a 1 on its input tape. (This restriction does not apply to the work tape.) A monotone alternating Turing machine is subject to the restriction that it can only reference an input bit x by, "there exists a z at most x," or "for all z at least x."

Then applying the result of [CKS81] that P = AL, mP is defined to be mAL: the class of decision problems solvable by a monotone alternating log-space Turing machine.

Actually there's a caveat: A monotone Turing machine or circuit can first negate the entire input, then perform a monotone computation. That way it becomes meaningful to talk about whether a monotone complexity class is closed under complement.

Strictly contained in mNP [Raz85].

Deciding whether a bipartite graph has a perfect matching, despite being both a monotone problem and in P, requires monotone circuits of superpolynomial size [Raz85b]. Letting MONO be the class of monotone problems, it follows that mP is strictly contained in MONO ∩ P.

See also: mNC¹, mL, mNL, mcoNL.

---

MP: Middle-Bit P

The class of decision problems such that for some #P function f, the answer on input x is 'yes' if and only if the middle bit of f(x) is 1.

Defined in [GKR+95].

Contains AmpMP and PH.

MP with ModP oracle equals MP with #P oracle [KT96].

---

MPC: Monotone Planar Circuits

The class of decision problems solvable by a family of monotone stratified planar circuits (a uniformity condition may also be imposed).

Such a circuit can contain only AND and OR gates of bounded fanin. It must be embeddable in the plane with no wires crossing. Furthermore, the input bits can only be accessed at the bottom level, where they are listed in order (x₁,...,x_n).

Defined in [DC89].

[BLM+99] showed that we can assume without loss of generality that the circuit has width n and depth n³.

---

mP/poly: Monotone P/poly

The class of decision problems solvable by a nonuniform family of polynomial-size Boolean circuits with only AND and OR gates, no NOT gates. (Or rather, following the definitions of [GS90], the entire input can be negated as long as there are no other negations.)

More straightforward to define than mP.

---

mTC⁰: Monotone TC⁰

The class of decision problems solvable by a family of monotone TC⁰ circuits (i.e. constant-depth, polynomial-size, AND, OR, and threshold gates, but no NOT gates).

A uniformity condition could also be imposed.

Defined in [GS90].

Strictly contained in mNC¹ [Yao89].

---

NAuxPDA^p: Nondeterministic Auxiliary Pushdown Automata

The class of problems solvable by nondeterministic logarithmic-space and polynomial-time Turing machines with auxiliary pushdown.

Equals LOGCFL [Sud78].

---

NC: Nick's Class

(Named in honor of Nick Pippenger.)

NCⁱ is the class of decision problems solvable by a nonuniform family of Boolean circuits, with polynomial size, depth O(logⁱ(n)), and fan-in 2.

Then NC is the union of NCⁱ over all nonnegative i.

Also, NC equals the union of PT/WK(log^kn, n^k)/poly over all constants k.

NCⁱ is contained in ACⁱ; thus, NC = AC.

Contains NL.

Generalizations include RNC and QNC.

[IN96] construct a candidate pseudorandom generator in NC based on the subset sum problem.

For a random oracle A, (NCⁱ)^A is strictly contained in (NCⁱ⁺¹)^A, and uniform NC^A is strictly contained in P^A, with probability 1 [Mil92].

---

NC⁰: Level 0 of NC

By definition, a decision problem in NC⁰ can depend on only a constant number of bits of the input. Thus, NC⁰ usually refers to functions computable by constant-depth, bounded-fanin circuits.

There is a family of permutations computable by a uniform family of NC⁰ circuits that is P-hard to invert [Has88].

Recently [AIK04] solved a longstanding open problem by showing that there exist pseudorandom generators and one-way functions in NC⁰, based on (for example) the hardness of factoring. Specifically, in these generators every bit of the output depends on only 4 input bits. Whether the dependence can be reduced to 3 bits under the same cryptographic assumptions is open, but [AIK04] have some partial results in this direction. It is known that the dependence cannot be reduced to 2 bits.

---

NC¹: Level 1 of NC

See NC for definition.

[KV94] give a family of functions that is computable in NC¹, but not efficiently learnable unless there exists an efficient algorithm for factoring Blum integers.

Was shown to equal 5-PBP [Bar89]. On the other hand, width 5 is necessary unless NC¹ = ACC⁰ [BT88].

As an application of this result, NC¹ can be simulated on a quantum computer with three qubits, one initialized to a pure state and the remaining two in the maximally mixed state [ASV00]. Surprisingly, [AMP02] showed that only a single qubit is needed to simulate NC¹ - i.e. that NC¹ is contained in 2-EQBP. (Complex amplitudes are needed for this result.)

Is contained in L [Bor77].

Contains TC⁰.

NC¹ contains the integer division problem [BCH86], even if an L-uniformity condition is imposed [CDL01].

---

NC²: Level 2 of NC

See NC for definition.

Contains NL.

---

NE: Nondeterministic E

Nondeterministic exponential time with linear exponent (i.e. NTIME(2^O(n))).

P^NE = NP^NE [Hem89].

Contained in NEXP.

---

Nearly-P: Languages Superpolynomially Close to P

The set of languages L such that for every k, there is a language L_k in P that differs from L on at most 2^n/n^k inputs of length n. Discussed in [NS05] and implicitly defined in [Yam99].

---

NE/poly: Nonuniform NE

Contains coNE, just as NEXP/poly contains coNEXP.

---

NEE: Nondeterministic EE

Nondeterministic double-exponential time with linear exponent (i.e. NTIME(2^{2^O(n)})).

If MA_E = NEE then MA = NEXP ∩ coNEXP [IKW01].

Contained in NEEXP.

---

NEEE: Nondeterministic EEE

Nondeterministic triple-exponential time with linear exponent.

---

NEEXP: Nondeterministic EEXP

Nondeterministic double-exponential time (i.e. NTIME(2^{2^p(n)}) for p a polynomial).

Equals MIP_EXP (unrelativized).

---

NEXP: Nondeterministic EXP

Nondeterministic exponential time (i.e. NTIME(2^p(n)) for p a polynomial).

Equals MIP [BFL91] (but not relative to all oracles).

NEXP is in P/poly if and only if NEXP = MA [IKW01].

[KI02] show the following:

• If P = RP, then NEXP is not computable by polynomial-size arithmetic circuits.
• If P = BPP and if checking whether a Boolean circuit computes a function that is close to a low-degree polynomial over a finite field is in P, then NEXP is not in P/poly.
• If NEXP is in P/poly, then matrix permanent is NEXP-complete.

Does not equal NP [SFM78].

Does not equal EXP if and only if there is a sparse set in NP that is not in P.

There exists an oracle relative to which EXP = NEXP but still P does not equal NP [Dek76].

The theory of reals with addition (see EXPSPACE) is hard for NEXP [FR74].

---

NEXP/poly: Nonuniform NEXP

Contains coNEXP (folklore result reported in [weblog]).

---

NIQSZK: Non-Interactive QSZK

Has the same relation to QSZK as NISZK does to SZK.

Defined in [Kob02], where it was also shown that the following promise problem is complete for NIQSZK. Given a quantum circuit, we are promised that the state it prepares (when run on the all-0 state, and tracing out non-output qubits) has trace distance either at most 1/3 or at least 2/3 from the maximally mixed state. The problem is to output "no" in the former case and "yes" in the latter.

NIQPZK can be defined similarly.

---

NISZK: Non-Interactive SZK

Defined in [DDP+98].

Contained in SZK.

[GSV99] showed the following:

• If SZK does not equal BPP then NISZK does not equal BPP.
• NISZK equals SZK if and only if NISZK is closed under complement.
• NISZK has natural complete promise problems:
• Statistical Distance from Uniform (SDU): Given a circuit, consider the distribution over outputs when the circuit is given a uniformly random n-bit string. We're promised that the trace distance between this distribution and the uniform distribution is either at most 1/3 or at least 2/3. The problem is to output "yes" in the former case and "no" in the latter.
• Entropy Approximation (EA): Now we're promised that the entropy of the circuit's output distribution is either at least k+1 or at most k-1. The problem is to output "yes" in the former case and "no" in the latter.

NIPZK can be defined similarly.

---

NISZK_h: NISZK With Limited Help

The non-interactive analogue of SZK_h.

Defined in [BG03], where the following was also shown:

• NISZK_h contains NISZK and is contained in SZK.
• Graph Isomorphism is in NISZK_h.
• The following problem is complete for NISZK_h: Given two functions from {0,1}ⁿ to {0,1}ⁿ (specified by circuits), decide whether their ranges are almost equal or almost disjoint, given that one of these is the case.

The quantum lower bound for the set comparison problem in [Aar02] implies an oracle relative to which NISZK_h is not in BQP.

---

NL: Nondeterministic Logarithmic-Space

Has the same relation to L as NP does to P.

In a breakthrough result, was shown to equal coNL [Imm88] [Sze87]. (Though contrast to mNL.)

Is contained in LOGCFL [Sud78], as well as NC².

Is contained in UL/poly [RA00].

Deciding whether a bipartite graph has a perfect matching is hard for NL [KUW86].

---

NL/poly: Nonuniform NL

Has the same relation to NL as P/poly does to P.

Is contained in ⊕L/poly [GW96], as well as SAC¹.

Equals UL/poly [RA00].

---

NLOG: NL With Nondeterministic Oracle Tape

Same as NL -- but if there's an oracle, then NLOG can make queries nondeterministically on a polynomial-size, one-way oracle tape. (NL, by contrast, can use nondeterministic transitions only on the worktape; oracle queries have to be deterministic.)

See [LL76] or [HCK+88] for more information.

Although NLOG is contained in P, there exists an oracle relative to which that is not the case. This illustrates that care is needed when defining oracle access mechanisms.

---

NLIN: Nondeterministic LIN

Has the same relation to LIN as NP does to P.

---

NONE: The Empty Class

The class that does not contain any languages. (It might not surprise you that I put this one in at the suggestion of a mathematician...)

Is the opposite of ALL, but does not equal the complement coALL = ALL.

Is closed under polynomial-time Turing reductions :-).

Equals SPARSE ∩ coSPARSE and TALLY ∩ coTALLY.

---

NP: Nondeterministic Polynomial-Time

The class of dashed hopes and idle dreams.

More formally: an "NP machine" is a nondeterministic polynomial-time Turing machine.

Then NP is the class of decision problems solvable by an NP machine such that

1. If the answer is "yes," at least one computation path accepts.
2. If the answer is "no," all computation paths reject.

Equivalently, NP is the class of decision problems such that, if the answer is "yes," then there is a proof of this fact, of length polynomial in the size of the input, that can be verified in P (i.e. by a deterministic polynomial-time algorithm). On the other hand, if the answer is "no," then the algorithm must declare invalid any purported proof that the answer is "yes."

For example, the SAT problem is to decide whether a given Boolean formula has any satisfying truth assignments. SAT is in NP, since a "yes" answer can be proved by just exhibiting a satisfying assignment.

A decision problem is NP-complete if (1) it is in NP, and (2) any problem in NP can be reduced to it (under some notion of reduction). The class of NP-complete problems is sometimes called NPC.

That NP-complete problems exist is immediate from the definition. The seminal result of Cook [Coo71], Karp [Kar72], and Levin [Lev73] is that many natural problems (that have nothing to do with Turing machines) are NP-complete.

The first such problem to be shown NP-complete was SAT [Coo71]. Other classic NP-complete problems include:

• 3-Colorability: Given a graph, can each vertex be colored red, green, or blue so that no two neighboring vertices have the same color?
• Hamiltonian Cycle: Given a graph, is there a cycle that visits each vertex exactly once?
• Traveling Salesperson: Given a set of n cities, and the distance between each pair of cities, is there a route that visits each city exactly once before returning to the starting city, and has length at most T?
• Maximum Clique: Given a graph, are there k vertices all of which are neighbors of each other?
• Subset Sum: Given a collection of integers, is there a subset of the integers that sums to exactly x?

For many, many more NP-complete problems, see [GJ79].

NP contains P. I've discovered a marvelous proof that NP and P are unequal, but this web page is too small to contain it. Too bad, since otherwise I'd be eligible for $1,000,000 [CMI00].

There exists an oracle relative to which P and NP are unequal [BGS75]. Indeed, P and NP are unequal relative to a random oracle with probability 1 [BG81] (see [AFM01] for a novel take on this result). Though random oracle results are not always indicative about the unrelativized case [CCG+94].

There even exists an oracle relative to which the P versus NP problem is outside the usual axioms of set theory [HH76].

If we restrict to monotone classes, mP is strictly contained in mNP [Raz85].

Perhaps the most important insight anyone has had into P versus NP is to be found in [RR97]. There the authors show that no 'natural proof' can separate P from NP (or more precisely, place NP outside of P/poly), unless secure pseudorandom generators do not exist. A proof is 'natural' if it satisfies two conditions called constructivity and largeness; essentially all lower bound techniques known to date satisfy these conditions. To obtain unnatural proof techniques, some people suspect we need to relate P versus NP to heavy-duty 'traditional' mathematics, for instance algebraic geometry. See [MS02] (and the survey article [Reg02]) for a development of this point of view.

For more on P versus NP (circa 1992) see [Sip92]. For an opinion poll, see [Gas02].

If P equals NP, then NP equals its complement coNP. Whether NP equals coNP is also open. NP and coNP can be extended to the polynomial hierarchy PH.

The set of decision problems in NP, but not in P or NPC, is sometimes called NPI. If P does not equal NP then NPI is nonempty [Lad75].

Probabilistic generalizations of NP include MA and AM. If NP is in coAM (or BPP) then PH collapses to Σ₂P [BHZ87].

PH also collapses to Σ₂P if NP is in P/poly [KL82].

There exist oracles relative to which NP is not in BQP [BBB+97].

An alternate characterization is NP = PCP(log n, O(1)) [ALM+98].

Also, [Fag74] gave a logical characterization of NP, which leads to the subclass SNP.

---

NPC: NP-Complete

The class of decision problems such that (1) they're in NP and (2) every problem in NP is reducible to them (under some notion of reduction). In other words, the hardest problems in NP.

Two notions of reduction from problem A to problem B are usually considered:

1. Karp or many-one reductions. Here a polynomial-time algorithm is given as input an instance of problem A, and must produce as output an instance of problem B.
2. Turing reductions, in this context also called Cook reductions. Here the algorithm for problem B can make arbitrarily many calls to an oracle for problem A.

Some examples of NP-complete problems are discussed under the entry for NP.

The classic reference on NPC is [GJ79].

Unless P = NP, NPC does not contain any sparse problems: that is, problems such that the number of 'yes' instances of size n is upper-bounded by a polynomial in n [Mah82].

A famous conjecture [BH77] asserts that all NP-complete problems are polynomial-time isomorphic -- i.e. between any two problems, there is a one-to-one and onto Karp reduction. If that's true, the NP-complete problems could be interpreted as mere "relabelings" of one another.

NP-complete problems are p-superterse unless P = NP [BKS95]. This means that, given k Boolean formulas F₁,...,F_k, if you can rule out even one of the 2^k possibilities in polynomial time (e.g., "if F₁,...,F_k-1 are all unsatisfiable then F_k is satisfiable"), then P = NP.

---

NP_C: NP Over The Complex Numbers

An analog of NP for Turing machines over a complex number field.

Defined in [BCS+97].

It is unknown whether P_C = NP_C, nor are implications known among this question, P_R versus NP_R, and P versus NP.

However, [CKK+95] show that if P/poly does not equal NP/poly then P_C does not equal NP_C.

[BCS+97] show the following striking result. For a positive integer n, let t(n) denote the minimum number of additions, subtractions, and multiplications needed to construct n, starting from 1. If for every sequence {n_k} of positive integers, t(n_k k!) grows faster than polylogarithmically in k, then P_C does not equal NP_C.

See also VNP_k.

---

NP^cc: Communication Complexity NP

The analogue of P^cc for nondeterministic communication complexity. Both communication bits and nondeterministic guess bits count toward the complexity.

Does not equal P^cc or coNP^cc because of the EQUALITY problem. Also, does not contain BPP^cc because of that problem.

Defined in [BFS86].

Contained in PH^cc.

---

NPI: NP-Intermediate

Sometimes used to denote the set of decision problems in NP that are neither NP-complete (that is, in NPC) nor in P.

Is thought to contain (for example) decision versions of factoring and graph isomorphism.

Is nonempty if P does not equal NP [Lad75]. Indeed, under this assumption, it contains an infinite number of distinct polynomial-time equivalence classes.

---

NP ∩ coNP

The class of problems in both NP and coNP.

Contains factoring [Pra75].

Contains graph isomorphism under the assumption that some language in NE ∩ coNE requires nondeterministic circuits of size 2^Ω(n) ([MV99], improving [KM99]). (A nondeterministic circuit C has two inputs, x and y, and accepts on x if there exists a y such that C(x,y)=1.)

Is not believed to contain complete problems.

---

(NP ∩ coNP)/poly: Nonuniform NP ∩ coNP

Together with NP/poly ∩ coNP/poly, has the same relation to NP ∩ coNP as P/poly has to P. A language in (NP ∩ coNP)/poly is defined by a single language in NP ∩ coNP which is then modified by advice. A language in NP/poly ∩ coNP/poly comes from two possibly different languages in NP and coNP which become the same with good advice.

There is an oracle relative to which NP/poly ∩ coNP/poly, indeed NP/1 ∩ coNP/1, is not contained in (NP ∩ coNP)/poly [FFK+93]. Recently they improved this to NP/1 ∩ coNP [FF..].

If NP is contained in (NP ∩ coNP)/poly, then PH collapses to S₂P^{NP ∩ coNP} [CCH+01].

---

NP/log: NP With Logarithmic Advice

Same as NP/poly, except that now the advice string is logarithmic-size.

---

NPMV: NP Multiple Value

The class of all (possibly partial, possibly multivalued) functions computed by an NP machine as follows: ignore the rejecting paths, and consider any output of an accepting path to be "one of the outputs."

Contains NPSV and NPMV_t.

Defined in [BLS84].

Contrast with FNP.

---

NPMV-sel: NPMV Selective

Has the same relation to NPMV as P-Sel does to P.

Defined in [HHN+95].

---

NPMV_t: NPMV Total

The class of all (possibly multivalued) NPMV functions that are total (that is, defined for every input).

---

NPMV_t-sel: NPMV_t Selective

Has the same relation to NPMV_t as P-Sel does to P.

Defined in [HHN+95].

---

NPO: NP Optimization

The class of function problems of the form, "Find any n-bit string x that maximizes a cost function C(x), where C is computable in FP (i.e. polynomial-time)."

Defined in [ACG+99].

Contains APX and NPOPB.

---

NPOPB: NPO Polynomially Bounded

The subclass of NPO problems for which the cost function is guaranteed always to be bounded by a polynomial in n (the input size).

See [ACG+99].

NPOPB equals the closure of MaxPB under PTAS reductions [CKS+99].

---

NP/poly: Nonuniform NP

Has the same relation to NP as P/poly does to P.

Contains AM. On the other hand, if NP/poly contains coNP then PH collapses to the third level.

NP/poly-natural proofs cannot show that circuit families are outside P/poly, under a pseudorandomness assumption [Rud97].

---

(NP,P-samplable): Average NP With Samplable Distributions

See AvgP for basic notions of average-case complexity.

(NP,P-samplable) is the same as DistNP, except that the distribution μ only needs to be samplable in polynomial time. μ's cumulative density function does not need to be computable in polynomial time.

Any problem complete for DistNP is also complete for (NP,P-samplable) [IL90].

---

NP_R: NP Over The Reals

An analog of NP for Turing machines over a real number field.

Defined in [BCS+97].

It is unknown whether P_R = NP_R, nor are implications known among this question, P_C versus NP_C, and P versus NP.

Also, in contrast to the case of NP_C, it is an open problem to show that P/poly distinct from NP/poly implies P_R distinct from NP_R. The difference is that in the real case, a comparison (or greater-than) operator is available, and it is not known how much power this yields in comparison to the complex case.

See also VNP_k.

---

NPSPACE: Nondeterministic PSPACE

Equals PSPACE [Sav70].

On the other hand, this result does not relativize if we allow strings of unbounded length to be written to the oracle tape. In particular, there exists an oracle relative to which NPSPACE is not contained in EXP [GTW+91].

---

NPSV: NP Single Value

The class of NPMV functions that are single-valued (i.e., such that every accepting path outputs the same value).

Defined in [BLS84].

Contains NPSV_t.

P = NP if and only if FP = NPSV.

---

NPSV-sel: NPSV Selective

Has the same relation to href="#npsv">NPSV as P-Sel does to P.

Defined in [HHN+95].

---

NPSV_t: NPSV Total

The class of all NPSV functions that are total (that is, defined on every input).

Contained in NPMV_t.

---

NPSV_t-sel: NPSV_t Selective

Has the same relation to NPSV_t as P-Sel does to P.

Also known as NP-sel.

Defined in [HHN+95].

---

NQP: Nondeterministic Quantum Polynomial-Time

The class of decision problems solvable by a QTM in polynomial time such that a particular '|Accept>' state has nonzero amplitude at the end of the computation, if and only if the answer is 'yes.' Since it has an exact amplitude condition, NQP has the same technical caveats as EQP. Or it would, except that it turns out to equal coC₌P [FGH+98].

Defined in [ADH97].

Contrast with QMA.

---

NSPACE(f(n)): Nondeterministic f(n)-Space

Same as NPSPACE, but with f(n)-space (for some constructible function f) rather than polynomial-space machines.

Contained in DSPACE(f(n)²) [Sav70], and indeed RevSPACE(f(n)²) [CP95].

NSPACE(n^k) is strictly contained in NSPACE(n^k+ε) for ε>0 [Iba72] (actually the hierarchy theorem is stronger than this, but pretty technical to state).

---

NT: Near-Testable

The class of decision problems such that whether the answer on input x agrees with the answer on input x-1 (that is, the lexicographic predecessor of x) is solvable in polynomial time. The Turing machine has to decide agreement or disagreement without access to the answer for x-1.

Is contained in E, NT*, and ⊕P. Defined in [GHJ+91] to study ⊕P-complete problems. They show that P, NT, NT*, and ⊕P are either all equal or strictly nested. In particular, they differ with probability 1 relative to a random oracle.

---

NT*: Near-Testable With Forest Ordering

Defined like NT, but with a more general ordering on inputs. A problem L is in NT* if, first, there is a partially defined predecessor function pred(x) in FP that organizes the space of inputs into a forest. The size of the lineage of each x must also be bounded by 2^poly(|x|). Second, if L(x) is the Boolean answer to L on input x, then L(x)+L(pred(x)) is computable in polynomial time; or if pred(x) does not exist, L(x) is computable in polynomial time.

Defined in [GHJ+91].

Contains NT and is contained in ⊕P. The inclusions are either both strict or both equalities (whence ⊕P = P as well).

---

NTIME(f(n)): Nondeterministic f(n)-Time

Same as NP, but with f(n)-time (for some constructible function f) rather than polynomial-time machines.

The Nondeterministic Time Hierarchy Theorem: If f and g are time-constructible and f(n+1)=o(g), then NTIME(f(n)) does not equal NTIME(g(n)) [SFM78] (this is actually stronger than the hierarchy theorem for DTIME).

NTIME(n) strictly contains DTIME(n) [PPS+83] (this result does not work for arbitrary f(n)).

For any constructible superpolynomial f, NTIME(f(n)) with NP oracle is not in P/poly [Kan82].

---

OCQ: One Clean Qubit

The class of problems solvable by a BQP machine in which a single qubit is initialized to the '0' state, and the remaining qubits are initialized to the maximally mixed state. (This definition is not known to be robust, so one also needs to specify a gate set.)

We also need to stipulate that there are no "strong measurements" -- intermediate measurements on which later operations are conditioned -- since otherwise we can do all of BQP by first initializing the computer to the all-0 state. Parker and Plenio [PP00] failed to appreciate this point.

Defined by [ASV00] (though they didn't use the name OCQ), who also showed that if OCQ = BQP, something other than gate-by-gate simulation will be needed to show this.

---

OptP: Optimum Polynomial-Time

The class of functions computable by taking the maximum of the output values over all accepting paths of an NP machine.

Defined in [Kre88].

Contrast with FNP.

---

P: Polynomial-Time

The class that started it all.

The class of decision problems solvable in polynomial time by a Turing machine. (See also FP, for function problems.)

Defined in [Edm65], [Cob64], [Rab60], and other seminal early papers.

Contains some highly nontrivial problems, including linear programming [Kha79] and finding a maximum matching in a general graph [Edm65].

Contains the problem of testing whether an integer is prime [AKS02], an important result that improved on a proof requiring an assumption of the generalized Riemann hypothesis [Mil76].

A decision problem is P-complete if it is in P, and if every problem in P can be reduced to it in L (logarithmic space). The canonical P-complete problem is circuit evaluation: given a Boolean circuit and an input, decide what the circuit outputs when given the input.

Important subclasses of P include L, NL, NC, and SC.

P is contained in NP, but whether they're equal seemed to be an open problem when I last checked.

Efforts to generalize P resulted in BPP and BQP.

The nonuniform version is P/poly, the monotone version is mP, and versions over the real and complex number fields are P_R and P_C respectively.

---

P/log: P With Logarithmic Advice

Same as P/poly, except that the advice string for input size n can have length at most logarithmic in n, rather than polynomial.

Strictly contained in IC[log,poly].

If NP is contained in P/log then P = NP.

---

P/poly: Nonuniform Polynomial-Time

The class of decision problems solvable by a family of polynomial-size Boolean circuits. The family can be nonuniform; that is, there could be a completely different circuit for each input length.

Equivalently, P/poly is the class of decision problems solvable by a polynomial-time Turing machine that receives an 'advice string,' that depends only on the size n of the input, and that itself has size upper-bounded by a polynomial in n.

Contains BPP by the progenitor of derandomization arguments [Adl78] [KL82]. By extension, BPP/poly, BPP/mpoly, and BPP/rpoly all equal P/poly. (By contrast, there is an oracle relative to which BPP/log does not equal BPP/mlog, while BPP/mlog and BPP/rlog are not equal relative to any oracle.)

[KL82] showed that, if P/poly contains NP, then PH collapses to the second level, Σ₂P.

They also showed:

• If PSPACE is in P/poly then PSPACE equals Σ₂P ∩ Π₂P.
• If EXP is in P/poly then EXP = Σ₂P.

It was later shown that, if NP is contained in P/poly, then PH collapses to ZPP^NP [KW98] and indeed S₂P [Cai01]. This seems close to optimal, since there exists an oracle relative to which the collapse cannot be improved to Δ₂P [Wil85].

If NP is not contained in P/poly, then P does not equal NP. Much of the effort toward separating P from NP is based on this observation. However, a 'natural proof' as defined by [RR97] cannot be used to show NP is outside P/poly, if there is any pseudorandom generator in P/poly that has hardness 2^{Ω(n^ε)} for some ε>0.

If NP is contained in P/poly, then MA = AM [AKS+95]

The monotone version of P/poly is mP/poly.

P/poly has measure 0 in E with Σ₂P oracle [May94b].

Strictly contains IC[log,poly] and P/log.

---

P^#P: P With #P Oracle

I decided this class is so important that it deserves an entry of its own, apart from #P.

Contains PH [Tod89], and is contained in PSPACE.

Equals P^PP (exercise for the visitor).

---

P^#P[1]: P With Single Query To #P Oracle

Contains PH [Tod89].

---

PAC⁰: Probabilistic AC⁰

The Political Action Committee for computational complexity research.

The class of problems for which there exists a DiffAC⁰ function f such that the answer is "yes" on input x if and only if f(x)>0.

Equals TC⁰ and C₌AC⁰ under logspace uniformity [ABL98].

---

PBP: Polynomial-Size Branching Program

Same as k-PBP but with no width restriction.

Equals L/poly [Cob66].

Contains P-OBDD.

---

k-PBP: Polynomial-Size Width-k Branching Program

A branching program is a directed acyclic graph with a designated start vertex. Each (non-sink) vertex is labeled by the name of an input bit, and has two outgoing edges, one of which is followed if that input bit is 0, the other if the bit is 1. A sink vertex can be either an 'accept' or a 'reject' vertex.

The size of the branching program is the number of vertices. The branching program has width k if the vertices can be sorted into levels, each with at most k vertices, such that each edge goes from a level to the one immediately after it.

Then k-PBP is the class of decision problems solvable by a family of polynomial-size, width-k branching programs. (A uniformity condition may also be imposed.)

k-PBP equals (nonuniform) NC¹ for constant k at least 5 [Bar89]. On the other hand, 4-PBP is in ACC⁰ [BT88].

Contained in k-EQBP, as well as PBP.

---

P_C: Polynomial-Time Over The Complex Numbers

An analog of P for Turing machines over a complex number field.

Defined in [BCS+97].

See also P_R, NP_C, NP_R, VP_k.

---

P^cc: Communication Complexity P

In a two-party communication complexity problem, Alice and Bob have n-bit strings x and y respectively, and they wish to evaluate some Boolean function f(x,y) using as few bits of communication as possible. P^cc is the class of (infinite families of) f's, such that the amount of communication needed is only O(polylog(n)), even if Alice and Bob are restricted to a deterministic protocol.

Is strictly contained in NP^cc and in BPP^cc because of the EQUALITY problem.

Equals NP^cc ∩ coNP^cc.

Defined in [BFS86].

---

PCD(r(n),q(n)): Probabilistically Checkable Debate

The class of decision problems decidable by a probabilistically checkable debate system, as follows.

Two debaters B and C alternate writing strings on a "debate tape," with B arguing that the answer is "yes" and C arguing the answer is "no." Then a polynomial-time verifier flips O(r(n)) random coins and makes O(q(n)) nonadaptive queries to the debate tape (meaning that they depend only on the input and the random coins, not the results of previous queries). The verifier then outputs an answer, which should be correct with high probability.

Defined in [CFL+93], who also showed that PCD(log n, 1) = PSPACE. This result was used to show that certain problems are PSPACE-hard even to approximate.

Contained in GPCD(r(n),q(n)).

---

P-Close: Problems Close to P

The class of decision problems solvable by a polynomial-time algorithm that outputs the wrong answer on only a sparse (that is, polynomially-bounded) set of instances.

---

PCP(r(n),q(n)): Probabilistically Checkable Proof

The class of decision problems such that a "yes" answer can be verified by a probabilistically checkable proof, as follows.

The verifier is a polynomial-time Turing machine with access to O(r(n)) uniformly random bits. It has random access to a proof (which might be exponentially long), but can query only O(q(n)) bits of the proof.

Then we require the following:

1. If the answer is "yes," there exists a proof such that the verifier accepts with certainty.
2. If the answer is "no," then for all proofs the verifier rejects with probability at least 1/2 (over the choice of the O(r(n)) random bits).

Defined in [AS98].

By definition NP = PCP(0,poly(n)).

MIP = PCP(poly(n),poly(n)).

PCP(r(n),q(n)) is contained in NTIME(2^O(r(n))q(n) + poly(n)).

NP = PCP(log n, log n) [AS98].

In fact, NP = PCP(log n, 1) [ALM+98]!

On the other hand, if NP is contained in PCP(o(log n), o(log n)), then P = NP [FGL+91].

Also, even though there exists an oracle relative to which NP = EXP [Hel84], if we could show there exists an oracle relative to which PCP(log n, 1) = EXP, then we'd have proved P not equal to NP [For94].

Another weird oracle fact: since NP does not equal NEXP [SFM78], PCP(0,log n) does not equal PCP(0,poly(n)). However, there exist oracles relative to which the latter inequality is false [HCC+92].

---

PermUP: Self-Permuting UP

The class of languages L in UP such that the mapping from an input x to the unique witness for x is a permutation of L.

Contains P.

Defined in [HT03], where it was also shown that the closure of PermUP under polynomial-time one-to-one reductions is UP.

On the other hand, they show that if PermUP = UP then E = UE.

See also: SelfNP.

---

PEXP: Probabilistic Exponential-Time

Has the same relation to EXP as PP does to P.

Is not contained in P/poly [BFT98].

---

PF: Alternate Name for FP

---

PFCHK(t(n)): Proof-Checker

The class of decision problems solvable in time O(t(n)) by a nondeterministic Turing machine, as follows. The machine is given oracle access to a proof string of unbounded length.

• If the answer is "yes," then there exists a value of the proof string such that all computation paths accept.
• If the answer is "no," then for all values of the proof string, there exists a computation path that rejects.

Credited in [For94] to S. Arora, R. Impagliazzo, and U. Vazirani.

An interesting question is whether NP = PFCHK(log n) relative to all possible oracles. Fortnow [For94] observes that the answer depends on what oracle access mechanism is used.

---

PH: Polynomial-Time Hierarchy

Let Δ₀P = Σ₀P = Π₀P = P. Then for i>0, let

• Δ_iP = P with Σ_i-1P oracle.
• Σ_iP = NP with Σ_i-1P oracle.
• Π_iP = coNP with Σ_i-1P oracle.

Then PH is the union of these classes for all nonnegative constant i.

PH can also be defined using alternating quantifiers: it's the class of problems of the form, "given an input x, does there exist a y such that for all z, there exists a w ... such that φ(x,y,z,w,...)," where y,z,w,... are polynomial-size strings and φ is a polynomial-time computable predicate. It's not totally obvious that this is equivalent to the first definition, since the first one involves adaptive NP oracle queries and the second one doesn't, but it is.

Defined in [Sto76].

Contained in P with a PP oracle [Tod89].

Contains BPP [Lau83].

Relative to a random oracle, PH is strictly contained in PSPACE with probability 1 [Cai86].

Furthermore, there exist oracles separating any Σ_iP from Σ_i+1P. On the other hand, it is unknown whether Σ_iP is strictly contained in Σ_i+1P relative to a random oracle with probability 1 (see [Has87]). Book [Boo94] shows that if PH collapses relative to a random oracle with probability 1, then it collapses unrelativized.

For a compendium of problems complete for different classes of the Polynomial Hierarchy see [Sch02a] and [Sch02b].

---

PH^cc: Communication Complexity PH

The obvious generalization of NP^cc and coNP^cc to a nondeterministic hierarchy.

It is unknown whether Σ₂^cc equals Π₂^cc.

Defined in [BFS86], where it was also shown (among other things) that BPP^cc is contained in Σ₂^cc ∩ Π₂^cc.

---

Φ₂P: Second Level of the Symmetric Hierarchy, Alternative Definition

The class of problems for which there exists a polynomial-time predicate P(x,y,z) such that for all x, if the answer on input x is "yes," then

1. For all y, there exists a z for which P(x,y,z).
2. For all z, there exists a y for which P(x,y,z).

Contained in Σ₂P and Π₂P.

Defined in [Can96], where it was also observed that Φ₂P = S₂P.

---

PhP: Physical Polynomial-Time

Defined by Valiant [Val03] to be "the class of physically constructible polynomial resource computers" (characterizing what "can be computed in the physical world in practice"). There he says that PhP contains P and BPP, but that it is open whether PhP contains BQP, since no scalable quantum computing proposal has been demonstrated beyond reasonable doubt.

For what it's worth, the present zookeeper has more qualms about admitting DTIME(n¹⁰⁰⁰) into PhP than BQTIME(n²). It is very possible that the total number of bits or bit tranisitions that can be witnessed by any one observer in the universe is finite. (Recent observations of the cosmological constant combined with plausible fundamental physics yields a bound of 10^k with k in the low hundreds.) In practice, less than 10⁵⁰ bits and less than 10⁸⁰ bit transitions are available for human use. (This is combining the number of atoms in the Earth with the number of signals that they can exchange in a millenium.)

The present veterinarian concurs that PhP is an unhealthy animal, although it is valid to ask whether BQP is a realistic class.

---

Π₂P: coNP With NP Oracle

Complement of Σ₂P.

Along with Σ₂P, comprises the second level of PH, the polynomial hierarchy. For any fixed k, there is a problem in Π₂P ∩ Σ₂P that cannot be solved by circuits of size n^k [Kan82].

---

PINC: Polynomial Ignorance of Names of Classes

(Actually, I've since been informed that PINC means "Incremental Polynomial-Time.")

The class of function problems, f:{0,1}ⁿ->{0,1}^m, such that the k^th output bit is computable in time polynomial in n and k.

Defined in [JY88].

Contained in PIO. This containment is strict, since if m=2ⁿ (say), then computing the first bit of f(x) might be EXP-complete.

---

PIO: Polynomial Input Output

The class of function problems, f:{0,1}ⁿ->{0,1}^m, such that f(x) is computable in time polynomial in n and m. Allows us to discuss whether a function is "efficiently computable" or not, even if the output is too long to write down in polynomial time.

Defined in [Yan81].

Strictly contains PINC.

---

P^K: P With Kolmogorov-Complexity Oracle

P equipped with an oracle that, given a string x, returns the length of the shortest program that outputs x.

A similar class was defined in [ABK+02], where it was also shown that P^K contains PSPACE. It is not known whether P^K contains all of R, or even any recursive problem not in PSPACE.

See also: BPP^KT.

---

PKC: Perfect Knowledge Complexity

Has the same relation to PZK as SKC does to SZK.

Defined in [GP91].

---

PL: Probabilistic L

Has the same relation to L that PP has to P.

Contains BPL.

PL^PL = PL (see [HO02]).

---

PL₁: Polynomially-Bounded L₁ Spectral Norm

The class of Boolean functions f:{-1,1}ⁿ->{-1,1} such that the sum of absolute values of Fourier coefficients of f is bounded by a polynomial in n.

Defined in [BS90], where it was also shown that PL₁ is contained in PT₁ (and this inclusion is strict).

---

PL_∞: Polynomially-Bounded L_∞^-1 Spectral Norm

The class of Boolean functions f:{-1,1}ⁿ->{-1,1} such that the maximum of |α|^-1, over all Fourier coefficients α of f, is upper-bounded by a polynomial in n.

Defined in [BS90], where it was also shown that PL_∞ contains PT₁ (and this inclusion is strict).

---

PLF: Polynomial Leaf

Defined in [Pap90].

I believe it's the same as PPA.

---

PLL: Polynomial Local Lemma

The class of TFNP function problems that are guaranteed to have a solution because of the Lovász Local Lemma. Defined in [Pap94b].

---

PLS: Polynomial Local Search

The subclass of TFNP function problems that are guaranteed to have a solution because of the lemma that "every finite directed acyclic graph has a sink."

More precisely, for each input, there's a finite set of solutions (i.e. strings), and a polynomial-time algorithm that computes a cost for each solution, and a neighboring solution of lower cost provided that one exists. Then the problem is to return any solution that has cost less than or equal to all of its neighbors. (In other words, a local optimum.)

(Note: In the Zookeeper's humble opinion, PLS should have been defined as follows: there exist polynomial-time algorithms that compute the cost of a solution, and the set of all neighbors of a given solution, not just a single solution of lower cost. Of course we'd require that every solution has only polynomially many neighbors. The two definitions are not obviously equivalent, and it's conceivable that knowing all the neighbors would be helpful -- for example, in simulated annealing one sometimes makes uphill moves.)

Defined in [JPY88], [PY88].

There exists an oracle relative to which PLS is not contained in FBQP [Aar03].

Also, there exist oracles relative to which PLS is not contained in PPA [BM04], and PPA and PPP are not contained in PLS [Mor01].

Whether PLS is not in PPP relative to some oracle remains open.

---

P^NP: P With Oracle Access To NP

See Δ₂P.

---

P^||NP: P With Parallel Queries To NP

Equals P^NP[log] ([BH91] and [Hem89] independently).

---

P^NP[k]: P With k NP Queries(for constant k)

Equals P with 2^k-1 parallel queries to NP (i.e. queries that do not depend on the outcomes of previous queries) ([BH91] and [Hem89] independently).

If P^NP[1] = P^NP[2], then P^NP[1] = P^NP[log] and indeed PH collapses to Δ₃P (attributed in [Har87b] to J. Kadin).

---

P^NP[log]: P With Log NP Queries

The class of decision problems solvable by a P machine, that can make O(log n) queries to an NP oracle (where n is the length of the input).

Equals P^||NP, the class of decision problems solvable by a P machine that can make polynomially many nonadaptive queries to an NP oracle (i.e. queries that do not depend on the outcomes of previous queries) ([BH91] and [Hem89] independently).

P^NP[log] is contained in PP [BHW89].

Determining the winner in an election system proposed in 1876 by Charles Dodgson (a.k.a. Lewis Carroll) has been shown to be complete for P^NP[log] [HHR97].

Contains P^NP[k] for all constants k.

---

P^{NP[log^2]}: P With Log² NP Queries

Same as P^NP[log], except that now log² queries can be made.

The model-checking problem for a certain temporal logic is P^{NP[log^2]}-complete [Sch03].

For all k, P with log^k adaptive queries to NP coincides with P with log^k+1 nonadaptive queries [CS92].

---

P-OBDD: Polynomial-Size Ordered Binary Decision Diagram

An ordered binary decision diagram (OBDD) is a branching program (see k-PBP), with the additional constraint that if x_i is queried before x_j on any path, then i<j.

Then P-OBDD is the class of decision problems solvable by polynomial-size OBDD's.

Contained in PBP, as well as BPP-OBDD.

---

PODN: Polynomial Odd Degree Node

The subclass of TFNP function problems that are guaranteed to have a solution because of the lemma that "every finite graph has an even number of odd-degree nodes."

Equals PPA [Pap90].

---

polyL: Polylogarithmic Space

Equals DSPACE((log n)^c).

In contrast to L, which is contained in P, it is not known if polyL is contained in P or vice versa. On the other hand, we do know that polyL does not equal P, since (for example) polyL does not have complete problems under many-to-one logspace reductions.

---

PostBQP: BQP With Postselection

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

• If the answer is 'yes' then the second qubit has at least 2/3 probability of being measured 1, conditioned on the first qubit having been measured 1.
• If the answer is 'no' then the second qubit has at most 1/3 probability of being measured 1, conditioned on the first qubit having been measured 1.
• On any input, the first qubit has a nonzero probability of being measured 1.

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):

• The quantum analogue of BPP_path.
• The class of problems solvable in quantum polynomial time if we allow arbitrary linear operations (not just unitary ones). Before measuring, we divide all amplitudes by a normalizing factor to make the probabilities sum to 1.
• The class of problems solvable in quantum polynomial time if we take the probability of measuring a basis state with amplitude α to be not |α|² but |α|^p, where p is an even integer greater than 2. (Again we need to divide all amplitudes by a normalizing factor to make the probabilities sum to 1.)

---

PP: Probabilistic Polynomial-Time

The class of decision problems solvable by an NP machine such that

1. If the answer is 'yes' then at least 1/2 of computation paths accept.
2. If the answer is 'no' then less than 1/2 of computation paths accept.

Defined in [Gil77].

PP is closed under union and intersection [BRS91] (this was an open problem for 14 years).

Contains P^NP[log] [BHW89].

Equals PP^BPP [KST+89b] as well as PostBQP [Aar05b].

However, there exists an oracle relative to which PP does not contain Δ₂P [Bei94].

PH is in P^PP [Tod89].

BQP is low for PP; i.e. PP^BQP = PP [FR98].

For a random oracle A, PP^A is strictly contained in PSPACE^A with probability 1 [ABF+94].

For any fixed k, there exists a language in PP that does not have circuits of size n^k [Vin04b]. Indeed, there exists a language in PP that does not even have quantum circuits of size n^k with quantum advice [Aar06].

By contrast, there exists an oracle relative to which PP has linear-size circuits [Aar06].

PP can be generalized to the counting hierarchy CH.

---

PP/poly: Nonuniform PP

Contains BQP/qpoly [Aar04b].

If PP/poly = P/poly then PP is contained in P/poly. Indeed this is true with any syntactically defined class in place of PP. An implication is that any unrelativized separation of BQP/qpoly from BQP/mpoly would imply that PP does not have polynomial-size circuits.

---

PPA: Polynomial Parity Argument

Defined in [Pap94b]; see also [BCE+95].

The subclass of TFNP function problems that are guaranteed to have a solution because of the lemma that "all graphs of maximum degree 2 have an even number of leaves."

More precisely, there's a polynomial-time algorithm that, given any string, computes its 'neighbor' strings (of which there are at most two). Then given a leaf string (i.e. one with only one neighbor), the problem is to output another leaf string.

As an example, suppose you're given a cubic graph (one where every vertex has degree 3), and a Hamiltonian cycle H on that graph. Then by making a sequence of modifications to H (albeit possibly exponentially many), it is always possible to find a second Hamilton cycle (see [Pap94]). So this problem is in PPA.

Another problem in PPA is finding an Arrow-Debreu equilibrium, given the goods and utility functions of traders in a marketplace.

Contained in TFNP.

Contains PPAD.

There exist oracles relative to which PPA does not contain PLS [BM04] and PPP [BCE+95]. There also exists an oracle relative to which PPA is not contained in PPP [BCE+95].

---

PPAD: Polynomial Parity Argument (Directed)

Defined in [Pap94b]; see also [BCE+95].

Same as PPA, except now the graph is directed, and we're asked to find either a source or a sink.

Contained in PPA and PPADS.

NASH, the problem of finding a Nash equilibrium in a normal form game of two or more players with specified utilities, is in PPAD [Pap94b], and proved to be complete for PPAD with four players in [DGP05], and shortly after extended to the case of three players [DP05] and independently [CD05].

There exists an oracle relative to which PPP is not contained in PPAD [BCE+95].

---

PPADS: Polynomial Parity Argument (Directed, Sink)

Defined in [Pap94b]; see also [BCE+95].

Same as PPA, except now the graph is directed, and we're asked to find a sink.

Contained in PPP.

Contains PPAD.

---

PPP: Polynomial Pigeonhole Principle

Defined in [Pap94b]; see also [BCE+95].

The subclass of TFNP function problems that are guaranteed to have a solution because of the Pigeonhole Principle.

More precisely, we're given a Boolean circuit, that maps n-bit strings to n-bit strings. The problem is to return either an input that maps to 0ⁿ, or two inputs that map to the same output.

Contained in TFNP.

Contains PPADS.

[BCE+95] give oracles relative to which PPP is not contained in PPA and PPAD, and PPA is not contained in PPP.

[Mor01] gives an oracle relative to which PPP is not contained in PLS.

Whether PLS is not contained in PPP relative to some oracle remains open.

---

P^PP: P With PP Oracle

A level of the counting hierarchy CH.

It is not known whether there exists an oracle relative to which P^PP does not equal PSPACE.

Contains PP^PH [Tod89].

Equals P^#P (exercise for the visitor).

Since the permanent of a matrix is #P-complete [Val79], Toda's theorem implies that any problem in the polynomial hierarchy can be solved by computing a sequence of permanents.

---

PQUERY: PSPACE With Polynomial Queries

The class of decision problems solvable in polynomial space using at most a polynomial number of queries to the oracle.

Thus, PQUERY = PSPACE, but PQUERY^A does not equal PSPACE^A for some oracles A.

Defined in [Kur83], where it was actually put forward as a serious argument (!!) against believing relativization results.

---

PPSPACE: Probabilistic PSPACE

Same as IPP, except that IPP uses private coins while PPSPACE uses public coins.

Can also be defined as a probabilistic version of PSPACE.

Equals PSPACE.

Defined in [Pap83].

---

PR: Primitive Recursive Functions

Basically, the class of functions definable by recursively building up arithmetic functions: addition, multiplication, exponentiation, tetration, etc. What's not allowed is to "diagonalize" a whole series of such functions to produce an even faster-growing one. Thus, the Ackermann function was proposed in 1928 as an example of a recursive function that's not primitive recursive, showing that PR is strictly contained in R.

An interesting difference is that PR functions can be explicitly enumerated, whereas functions in R cannot be (since otherwise the halting problem would be decidable). That is, PR is a "syntactic" class whereas R is "semantic."

On the other hand, we can "enumerate" any RE set by a PR function in the following sense: given an input (M,k), where M is a Turing machine and k is an integer, if M halts within k steps then output M; otherwise output nothing. Then the union of the outputs, over all possible inputs (M,k), is exactly the set of M that halt.

PR strictly contains ELEMENTARY.

---

P_R: Polynomial-Time Over The Reals

An analog of P for Turing machines over a real number field.

Defined in [BCS+97].

See also P_C, NP_C, NP_R, VP_k.

---

Pr_HSPACE(f(n)): Unbounded-Error Halting Probabilistic f(n)-Space

Has the same relation to DSPACE(f(n)) as PP does to P. The Turing machine has to halt on every input and every setting of the random tape.

Equals PrSPACE(f(n)) [Jun85].

---

PromiseBPP: Promise-Problem BPP

Same as PromiseRP, but for BPP instead of RP.

Defined in [BF99].

---

PromiseBQP: Promise-Problem BQP

Same as PromiseBQP, but for BQP instead of BPP.

If PromiseBQP = PromiseP then BQP/mpoly = P/poly.

---

PromiseP: Promise-Problem P

The class of promise problems solvable by a P machine.

---

PromiseRP: Promise-Problem RP

The class of promise problems solvable by an RP machine. I.e., the machine must accept with probability at least 1/2 for "yes" inputs, and with probability 0 for "no" inputs, but could have acceptance probability between 0 and 1/2 for inputs that do not satisfy the promise.

Defined in [BF99], where it was also shown that BPP is in RP^PromiseRP[1] (i.e. with a single oracle query to PromiseRP).

Contained in PromiseBPP.

---

PrSPACE(f(n)): Unbounded-Error Probabilistic f(n)-Space

Has the same relation to DSPACE(f(n)) as PP does to P. The Turing machine has to halt with probability 1 on every input.

Contained in DSPACE(f(n)²) [BCP83].

Equals Pr_HSPACE(f(n)) [Jun85].

---

P-Sel: P-Selective Sets

The class of decision problems for which there's a polynomial-time algorithm with the following property. Whenever it's given two instances, a "yes" and a "no" instance, the algorithm can always decide which is the "yes" instance.

Defined in [Sel79], where it was also shown that if NP is contained in P-Sel then P = NP.

There exist P-selective sets that are not recursive (i.e. not in R).

---

PSK: Polynomial Sink

Yeah, I'm told that's what the S and K stand for. Go figure.

The class of total function problems definable as follows: given a directed graph of indegree and outdegree at most 1, and given a source, find a sink.

Defined in [Pap90].

Equals PPADS.

---

PSPACE: Polynomial-Space

The class of decision problems solvable by a Turing machine in polynomial space.

Equals NPSPACE [Sav70], AP [CKS81], IP [Sha90], and, assuming the existence of one-way functions, CZK [BGG+90].

Contains P with #P oracle.

A canonical PSPACE-complete problem is Quantified Boolean Formula (QBF): Given a Boolean formula with universal and existential quantifiers, decide whether it's true or false.

Relative to a random oracle, PSPACE strictly contains PH with probability 1 [Cai86].

PSPACE has a complete problem that is both downward self-reducible and random self-reducible [TV02]. It is the largest class with such a complete problem.

Contained in EXP. There exists an oracle relative to which this containment is proper [Dek76].

---

PSPACE/poly: PSPACE With Polynomial-Size Advice

Contains QMA/qpoly [Aar06b].

---

PT₁: Polynomial Threshold Functions

The class of Boolean functions f:{-1,1}ⁿ->{-1,1} such that f(x)=sgn(p(x)), where p is a polynomial having a number of terms polynomial in n.

Defined in [BS90], where it was also shown that PT₁ contains PL₁ (and this inclusion is strict), and that PT₁ is contained in PL_∞ (and this inclusion is strict).

---

PTAPE: Archaic for PSPACE

---

PTAS: Polynomial-Time Approximation Scheme

The subclass of NPO problems that admit an approximation scheme in the following sense. For any ε>0, there is a polynomial-time algorithm that is guaranteed to find a solution whose cost is within a 1+ε factor of the optimum cost. (However, the exponent of the polynomial might depend strongly on ε.)

Contains FPTAS, and is contained in APX.

As an example, the Traveling Salesman Problem in the Euclidean plane is in PTAS [Aro96].

Defined in [ACG+99].

---

PT/WK(f(n),g(n)): Parallel Time f(n) / Work g(n)

The class of decision problems solvable by a uniform family of Boolean circuits with depth upper-bounded by f(n) and size (number of gates) upper-bounded by g(n).

The union of PT/WK(log^kn, n^k) over all constants k equals NC.

---

PZK: Perfect Zero Knowledge

Same as SZK, but now the two distributions must be identical, not merely statistically close. (The "two distributions" are (1) the distribution over Arthur's view of his interaction with Merlin, conditioned on Arthur's random coins, and (2) the distribution over views that Arthur can simulate without Merlin's help.)

Contained in SZK.

See also: CZK.

---

Q: Quasi-Realtime Languages

The class of problems solvable by a nondeterministic multitape Turing machine in linear time. Defined in [BG69], where it was shown that Q equals the class of problems solvable by a nondeterministic multitape Turing machine in exactly n steps (as opposed to O(n) steps).

Contains GCSL.

---

QAC⁰: Quantum AC⁰

The class of decision problems solvable by a family of constant-depth, polynomial-size quantum circuits. Here each layer of the circuit is a tensor product of one-qubit gates and Toffoli gates, or is a tensor product of controlled-NOT gates.

A uniformity condition may also be imposed.

Defined in [Moo99].

Contains AC⁰, and is contained in QAC_f⁰.

---

QAC⁰[m]: Quantum AC⁰[m]

Same as QAC⁰, except that now Mod-m gates are also allowed. A Mod-m gate computes whether the sum of a given set of bits is congruent to 0 modulo m, and exclusive-OR's the answer into another bit.

Defined in [Moo99].

---

QACC⁰: Quantum ACC⁰

Same as QAC⁰[m], except that Mod-m gates are allowed for any m.

Defined in [Moo99].

[GHP00] showed that QACC⁰ equals QAC⁰[p] for any prime p.

---

QAC_f⁰: QAC⁰ With Fanout

Same as QAC⁰, except that an additional "quantum fanout" gate is available, which CNOT's a qubit into arbitrarily many target qubits in a single step.

Defined in [Moo99], where it was also shown that QAC_f⁰ = QAC⁰[2] = QACC⁰.

---

QAM: Quantum AM

The class of decision problems for which a "yes" answer can be verified by a public-coin quantum AM protocol, as follows. Arthur generates a uniformly random (classical) string and sends it to Merlin. Merlin responds with a polynomial-size quantum certificate, on which Arthur can perform any BQP operation. The completeness and soundness requirements are the same as for AM.

Defined by Marriott and Watrous [MW05].

Contains QMA and is contained in QIP[2] and BP•PP (and therefore PSPACE).

---

QCFL: Quantum CFL

The class of decision problems recognized by quantum context-free languages, which are defined in [MC00]. The authors also showed that QCFL does not equal CFL.

---

QCMA: Quantum Classical MA

The class of decision problems for which a "yes" answer can be verified by a quantum computer with access to a classical proof.

Contains MA, and is contained in QMA.

Given a black-box group G and a subgroup H, the problem of testing non-membership in H has polynomial QCMA query complexity [AK06].

See [AK06] for a "quantum oracle separation" between QCMA and QMA. No classical oracle separation between QCMA and QMA is currently known.

---

QH: Query Hierarchy Over NP

QH_i is defined to be P^NP[k]; that is, P with k queries to an NP oracle (where k is a constant). Then QH is the union of QH_i over all nonnegative i.

QH = BH [Wag88]; thus, either both hierarchies are infinite or both collapse to some finite level.

---

QIP: Quantum IP

The class of decision problems such that a "yes" answer can be verified by a quantum interactive proof. Here the verifier is a BQP (i.e. quantum polynomial-time) algorithm, while the prover has unbounded computational resources (though cannot violate the linearity of quantum mechanics). The prover and verifier exchange a polynomial number of messages, which can be quantum states. Thus, the verifier's and prover's states may become entangled during the course of the protocol. Given the verifier's algorithm, we require that

1. If the answer is "yes," then the prover can behave in such a way that the verifier accepts with probability at least 2/3.
2. If the answer is "no," then however the prover behaves, the verifier rejects with probability at least 2/3.

Let QIP[k] be QIP where the prover and verifier are restricted to exchanging k messages (with the prover going last).

Defined in [Wat99], where it was also shown that PSPACE is in QIP[3].

Subsequently [KW00] showed that for all k>3, QIP[k] = QIP[3] = QIP.

QIP is contained in EXP [KW00].

QIP(1) is more commonly known as QMA.

See also: QIP[2], QSZK.

---

QIP[2]: 2-Message Quantum IP

See QIP for definition.

Contains QSZK [Wat02].

---

QMA: Quantum MA

The class of decision problems such that a "yes" answer can be verified by a 1-message quantum interactive proof. That is, a BQP (i.e. quantum polynomial-time) verifier is given a quantum state (the "proof"). We require that

1. If the answer is "yes," then there exists a state such that verifier accepts with probability at least 2/3.
2. If the answer is "no," then for all states the verifier rejects with probability at least 2/3.

QMA = QIP(1).

Defined in [Wat00], where it is also shown that group non-membership is in QMA. That is: let G be a group, whose elements are represented by polynomial-size strings. We're given a "black box" that correctly multiplies and inverts elements of G. Then given elements g and h₁,...,h_k, we can verify in QMA that g is not in the subgroup generated by h₁,...,h_k.

Based on this, [Wat00] gives an oracle relative to which MA is strictly contained in QMA.

Kitaev and Watrous (unpublished) showed QMA is contained in PP. Combining that result with [Ver92], one can obtain an oracle relative to which AM is not in QMA.

Kitaev ([KSV02], see also [AN02]) showed that the following problem is complete for QMA:

5-Local Hamiltonians. Given an n-qubit Hilbert space, as well as a collection H₁,...,H_k of Hamiltonians (i.e. Hermitian positive semidefinite matrices), each of which acts on at most 5 qubits of the space. Also given reals a,b such that b-a = Θ(1/poly(n)). Decide whether the smallest eigenvalue of H=H₁+...+H_k is less than a or greater than b, promised that one of these is the case. Subsequently Kempe and Regev [KR03] showed that even 3-Local Hamiltonians is QMA-complete. A subsequent paper by Kempe, Kitaev, and Regev [KKR04], has hit rock bottom (assuming P does not equal QMA), by showing 2-local Hamiltonians QMA-complete.

Compare to NQP.

If QMA = PP then PP contains PH [Vya03]. This result uses the fact that QMA is contained in A₀PP.

See also: QCMA, QMA/qpoly, QSZK, QMA(2), QMA-plus.

---

QMA-plus: QMA With Super-Verifier

Same as QMA, except now the verifier can directly obtain the probability that a given observable of the certificate state, if measured, would equal 1. (In the usual model, by contrast, one can only sample an observable.)

Defined in [AR03], where it was also shown that QMA-plus = QMA.

---

QMA(2): Quantum MA With Multiple Certificates

Same as QMA, except that now the verifier is given two polynomial-size quantum certificates, which are guaranteed to be unentangled.

Defined in [KMY01]. It is unknown whether QMA(k) = QMA(2) for all k>2, and also whether QMA(2) = QMA.

---

QMA_log: QMA With Logarithmic-Size Proofs

Same as QMA except that the quantum proof has O(log n) qubits instead of a polynomial number.

Equals BQP [MW05].

---

QMAM: Quantum Merlin-Arthur-Merlin Public-Coin Interactive Proofs

The class of decision problems for which a "yes" answer can be verified by a public-coin quantum MAM protocol, as follows. Merlin sends a polynomial-size quantum state to Arthur. Arthur then flips some classical coins (in fact, he only has to flip one without loss of generality) and sends the outcome to Merlin. At this stage Arthur is not yet allowed to perform any quantum operations. Merlin then sends Arthur another quantum state. Finally, Arthur performs a BQP operation on both of the states simultaneously, and either accepts or rejects. The completeness and soundness requirements are the same as for AM. Also, Merlin's messages might be entangled.

Defined by Marriott and Watrous [MW05], who also showed that QMAM = QIP(3) = QIP.

Hence QMAM contains PSPACE.

---

QMA/qpoly: QMA With Polynomial-Size Quantum Advice

Is contained in PSPACE/poly [Aar06b].

---

QMIP: Quantum Multi-Prover Interactive Proofs

The quantum generalization of MIP, and the multi-prover generalization of QIP.

A quantum multi-prover interactive proof system is the same as a classical one, except that all messages and verifier computations are quantum. As in MIP, there is no communication among the provers; however, the provers share unlimited prior entanglement. The number of provers and number of rounds can both be polynomial in n.

Defined in [KM02].

Fascinatingly, no relationship between QMIP and NEXP is known. We don't know whether allowing the provers unlimited prior entanglement makes the class more powerful, less powerful, or both!

---

QMIP_le: Quantum Multi-Prover Interactive Proofs With Limited Prior Entanglement

Same as QMIP, except that now the provers share only a polynomial number of EPR pairs, instead of an unlimited number.

Defined in [KM02], where it was also shown that QMIP_le is contained in NEXP = QMIP_ne.

---

QMIP_ne: Quantum Multi-Prover Interactive Proofs With No Prior Entanglement

Same as QMIP, except that now the provers have no prior entanglement.

Defined in [KM02], where it was also shown that QMIP_ne = NEXP. Thus, QMIP_ne contains QMIP_le.

---

QNC: Quantum NC

The class of decision problems solvable by polylogarithmic-depth quantum circuits with bounded probability of error. (A uniformity condition may also be imposed.)

Has the same relation to NC as BQP does to P.

[CW00] showed that factoring is in ZPP with a QNC oracle.

Is incomparable with BPP as far as anyone knows.

See also: RNC.

---

QNC⁰: Quantum NC⁰

Constant-depth quantum circuits without fanout gates.

Defined in [Spa02].

Contained in QNC_f⁰.

---

QNC_f⁰: Quantum NC⁰ With Unbounded Fanout

Constant-depth quantum circuits with unbounded-fanout gates.

Defined in [Spa02].

Contains QNC⁰, and is contained in QACC⁰.

---

QNC¹: Quantum NC¹

Same as QNC¹, but for the exact rather than bounded-error case.

In contrast to NC¹, it is not clear how to simulate QNC¹ on a quantum computer in which one qubit is initialized to a pure state, and the remaining qubits are in the maximally mixed state [ASV00].

See also [MN02].

---

QP: Quasipolynomial-Time

Equals DTIME(2^polylog(n)).

---

QPLIN: Linear Quasipolynomial-Time

Equals DTIME(n^{O(log n)}).

Has the same relationship to QP that E does to EXP.

---

QPSPACE: Quasipolynomial-Space

Equals DSPACE(2^polylog(n)).

According to [BG94], Beigel and Feigenbaum and (independently) Krawczyk showed that QPSPACE is not contained in Check.

---

QRG: Quantum Refereed Games

Same as RG, except that now the verifier is a BQP machine, and can exchange polynomially many quantum messages with the competing provers.

The two provers are computationally unbounded, but must obey the laws of quantum mechanics. Also, we can assume without loss of generality that the provers share no entanglement, because adversaries gain no advantage by sharing information.

Defined in [Gut05], where it was also shown that QRG is contained in NEXP ∩ coNEXP.

QRG trivially contains RG (and hence EXP), as well as SQG.

---

QS₂P: Quantum S₂P

The class of problems for which there exists a BQP machine M such that:

• If the answer is "yes," then there exists a quantum state ρ such that for all quantum states σ, M(ρ,Ï) accepts with probability at least 2/3.
• If the answer is "no," then there exists a σ such that for all ρ, M(ρ,σ) rejects with probability at least 2/3.

In other words, it's the same as SQG, but without communication from the verifier back to the provers.

Contains QMA (and indeed P^QMA), and is contained in SQG and hence EXP.

---

QSZK: Quantum Statistical Zero-Knowledge

A quantum analog of SZK (or more precisely HVSZK).

Arthur is a BQP (i.e. quantum) verifier who can exchange quantum messages with Merlin. So Arthur and Merlin's states may become entangled during the course of the protocol.

Arthur's "view" of his interaction with Merlin is taken to be the sequence of mixed states he has, over all steps of the protocol. The zero-knowledge requirement is that each of these states must have trace distance at most (say) 1/10 from a state that Arthur could prepare himself (in BQP), without help from Merlin. Arthur is assumed to be an honest verifier.

Defined in [Wat02], where the following was also shown:

• QSZK is contained in PSPACE.
• QSZK is closed under complement.
• Any protocol can be parallelized to consist of two messages, so that QSZK is in QIP[2].
• One can assume without loss of generality that protocols are public-coin, as for SZK.
• QSZK has a natural complete promise problem, called Quantum State Distinguishability (QSD). We are given quantum circuits Q₀ and Q₁. Let ρ₀ and ρ₁ be the mixed states they produce respectively, when run on the all-0 state (and when non-output qubits are traced out). We are promised that the trace distance between ρ₀ and ρ₁ is either at most α or at least β, where α and β are constants in [0,1] satisfying α < β². The problem is to decide which of these is the case.

---

R: Recursive Languages

The class of decision problems solvable by a Turing machine. Often identified with the class of 'effectively computable' functions (the Church-Turing thesis).

Defined in [Tur36], [Chu41], and other seminal early papers.

Equals RE ∩ coRE.

Strictly contains PR, the primitive recursive functions (see [Kle71]).

---

RBQP: Strict Quantum RP

The class of problems in NP whose witnesses are in FBQP. For example, the set of square-free numbers is in coRBQP using only the fact that factoring is in FBQP. (Even without a proof that the factors are prime, the factorization proves that there is a square divisor.)

Contains RP and ZBQP, and is contained in BQP and RQP. Defined here to clarify EQP; see also ZBQP.

---

RE: Recursively Enumerable Languages

The class of decision problems for which a 'yes' answer can be verified by a Turing machine in a finite amount of time. (If the answer is 'no,' on the other hand, the machine might never halt.)

Equivalently, the class of decision problems for which a Turing machine can list all the 'yes' instances, one by one (this is what 'enumerable' means).

A problem C is complete for RE if (1) C is in RE and (2) any problem in RE can be reduced to C by a Turing machine.

Actually there are two types of reduction: M-reductions (for many-one), in which a single instance of the original problem is mapped to an instance of C, and T-reductions (for Turing), in which an algorithm for the original problem can make arbitrarily many calls to an oracle for C.

RE-complete sets are also called creative sets for some reason.

The canonical RE-complete problem is the halting problem: i.e., given a Turing machine, does it halt when started on a blank tape?

The famous unsolvability of the halting problem [Tur36] implies that R does not equal RE.

Also, RE does not equal coRE.

RE and coRE can be generalized to the arithmetic hierarchy AH.

There are problems in RE that are neither RE-complete under T-reductions, nor in R [Fri57] [Muc56]. This is the resolution of Post's problem [Pos44].

Indeed, RE contains infinitely many nonequivalent 'T-degrees.' (A T-degree is a class of problems, all of which can be T-reduced to one another.) The structure of the T-degrees has been studied in more detail than you can possibly imagine [Sho99].

---

REG: Regular Languages

The class of decision problems solvable by deterministic finite automata (DFA's).

Equals the class solvable by nondeterministic finite automata (NDFA's).

Equals DSPACE(O(1)) [She59], which equals DSPACE(o(log log n)) [HLS65].

Includes, i.e., "Is the parity of the input odd?," but not "Are the majority of bits in the input 1's?" This is sometimes expressed as "finite automata can't count."

Contained in NC¹.

See e.g. [Koz97], [Gur89] for basic results on regular languages.

---

RevSPACE(f(n)): Reversible f(n)-Space

The class of decision problems solvable in space O(f(n)) by a reversible Turing machine (a deterministic Turing machine for which every configuration has at most one immediate predecessor).

Was shown to equal DSPACE(f(n)) [LMT97].

---

RG: Refereed Games

The class of problems solvable by a probabilistic polynomial-time verifier who can exchange a polynomial number of messages with two competing, computationally-unbounded provers -- one trying to convince the verifier that the answer is "yes," the other that the answer is "no." Note that the verifier can hide information from the provers. Public-coin RG amounts to SAPTIME, which equals PSPACE [Pap83].

RG is in EXP relative to any oracle [KM92]; they are equal, unrelativized [FK97b].

Contains RG[1], and is contained in QRG.

See also PCD, GPCD.

---

RG[1]: One-Round Refereed Games

Same as RG, except that now the verifier can exchange only a single round of messages with the two provers. A round consists of private messages from the verifier to the provers, followed by private responses from the provers to the verifier. Since the queries are private, they may as well be parallel; likewise the responses. This makes RG[1] a symmetric class, indeed a randomized analogue of S₂P.

RG[1] is contained in PSPACE, and they are equal, unrelativized [FK97b].

Contains S₂P and is contained in SQG.

---

R_HL: Randomized Halting Logarithmic-Space

Has the same relation to L as RP does to P. The randomized machine must halt for every input and every setting of the random tape.

Contains undirected reachability (is there a path from vertex u to vertex v in an undirected graph?) [AKL+79].

Contained in RL.

---

R_HSPACE(f(n)): One-Sided Error Halting Probabilistic f(n)-Space

Has the same relation to BP_HSPACE(f(n)) as RP does to BPP.

---

RL: Randomized Logarithmic-Space

Has the same relation to L as RP does to P. The randomized machine must halt with probability 1 on any input. It must also run in polynomial time (since otherwise we would just get NL).

Contains R_HL.

Contained in SC [Nis92].

[RTV05] give strong evidence that RL = L.

---

RNC: Randomized NC

Has the same relation to NC as RP does to P.

Contains the maximum matching problem for bipartite graphs [MVV87].

Contained in QNC.

See also: coRNC.

---

RP: Randomized Polynomial-Time

The class of decision problems solvable by an NP machine such that

1. If the answer is 'yes,' at least 1/2 of computation paths accept.
2. If the answer is 'no,' all computation paths reject.

Defined in [Gil77].

Contains the problem of testing whether an integer is prime [AH87].

For other problems in RP, see the standard text on randomized algorithms, [MR95].

See also: coRP, ZPP, BPP.

---

RPP: Restricted Pseudo Polynomial-Time

The class of decision problems (x,m) (where x is an input of length |x|=n and m is an integer parameter), that are solvable by a nondeterministic (i.e. NP) machine in poly(n+m) time and O(m+log n) space simultaneously.

Defined in [Mon80].

See also FPT.

---

RQP: One-sided Error Extension of EQP

The class of questions that can be answered by a QTM that accepts with probability 0 when the true answer is no, and accepts with probability at least 1/2 when the true answer is yes. Since one of the probabilities has to vanish, RQP has the same technical caveats as EQP.

Contains ZQP and RBQP, and is contained in BQP.

---

RSPACE(f(n)): Randomized f(n)-Space

Same as RL, but for O(f(n))-space instead of logarithmic-space.

Contained in NSPACE(f(n)) and BPSPACE(f(n)).

---

S₂P: Second Level of the Symmetric Hierarchy

The class of decision problems for which there is a polynomial-time predicate P such that, on input x,

1. If the answer is 'yes,' then there exists a y such that for all z, P(x,y,z) is true.
2. If the answer is 'no,' then there exists a z such that for all y, P(x,y,z) is false.

Note that this differs from Σ₂P in that the quantifiers in the second condition are reversed.

Less formally, S₂P is the class of one-round games in which a prover and a disprover submit simultaneous moves to a deterministic, polynomial-time referee. In Σ₂P, the disprover moves first.

Defined in [RS98], where it was also shown that S₂P contains MA and Δ₂P. Defined independently in [Can96].

Contained in ZPP^NP [Cai01].

---

[edit] S2-EXP•PNP: Don't Ask One of the caged classes of the Complexity Zoo. Has been implicated in a collapse scandal involving AM[polylog], coNP, and EH.

---

SAC: Semi-Unbounded-Fanin AC

SAC^k is the class of decision problems solvable by a family of depth-O(log^kn) circuits with unbounded-fanin OR and bounded-fanin AND gates. Negations are only allowed at the input level.

A uniformity condition may also be imposed.

Defined by [BCD+89], who also showed that SAC_k is closed under complement for every k>0.

---

SAC⁰: Semi-Unbounded-Fanin AC⁰

See SAC for definition.

Not closed under complement [BCD+89].

---

SAC¹: Semi-Unbounded-Fanin AC¹

See SAC for definition.

Equals LOGCFL/poly [Ven91].

Contained in ⊕SAC¹ [GW96].

---

SAPTIME: Stochastic Alternating Polynomial-Time

The class of problems solvable by a polynomial-time Turing machine with three kinds of quantifiers: existential, universal, and randomized.

Defined in [Pap83], where it was also observed that SAPTIME = PSPACE.

---

SBP: Small Bounded-Error Probability

The class of decision problems for which the following holds. There exists a #P function f and an FP function g such that, for all inputs x,

1. If the answer is "yes" then f(x) > g(x).
2. If the answer is "no" then f(x) < g(x)/2.

Defined in [BGM02], where the following was also shown:

• SBP contains MA, WAPP, and ∃BPP.
• SBP is contained in AM and BPP_path.
• There exists an oracle relative to which SBP is not contained in Σ₂P.
• SBP is closed under union.

---

SC: Steve's Class

(Named in honor of Stephen Cook.)

The class of decision problems solvable by a Turing machine that simultaneously uses polynomial time and polylogarithmic space.

Note that SC might be smaller than P ∩ polyL, since for the latter, it suffices to have two separate algorithms: one polynomial-time and the other polylogarithmic-space.

Deterministic context-free languages (DCFL's) can be recognized in SC [Coo79].

SC contains RL and BPL [Nis92].

SC equals DTISP(poly,polylog) by definition.

---

SE: Subexponentially-Solvable Search Problems

The class of FNP search problems solvable in O(2^εn) time for every ε>0.

Defined in [IPZ01], who also gave reductions showing that if any of k-SAT, k-colorability, k-set cover, clique, or vertex cover is in SE, then all of them are.

---

SEH: Strong Exponential Hierarchy

The union of NE, NP^NE, NP^{NP^NE}, and so on.

Is called "strong" to contrast it with the ordinary Exponential Hierarchy EH.

Note that we would get the same class if we replaced NE by NEXP.

SEH collapses to P^NE [Hem89]

There exists an oracle relative to which SEH is not contained in EH [Hem89]. EH and SEH are incomparable for all anyone knows.

---

SelfNP: Self-Witnessing NP

The class of languages L in NP such that the union, over all x in L, of the set of valid witnesses for x equals L itself.

Defined in [HT03], where it was shown that the closure of SelfNP under polynomial-time many-one reductions is NP.

They also show that if SelfNP = NP, then E = NE; and that SAT is contained in SelfNP.

See also: PermUP.

---

SF_k: Width-k Bottleneck Turing Machines

The class of decision problems solvable by a k-bottleneck Turing machine. This is a machine that, after a polynomial amount of time, erases everything on the tape except for a single k-valued "safe-storage". There's also a counter recording the number of erasings, which is in effect a non-deterministic witness. For example, SF₂ contains both ⊕P and NP by using the counter as a witness.

Defined in [CF91], where it was also shown that SF₅ = PSPACE.

The complexity of SF₂, SF₃, and SF₄ was studied in [Ogi94] and [Her97]. The following result of those authors is among the caged beasts of the Complexity Zoo:

SF4 is contained in BP ⊕PMod_3P ^ ⊕P ^ Mod_3P ^ ⊕P

(Here the BP operator means that one makes the class into a bounded-error probabilistic class, the same way one makes P into BPP and NP into AM.)

---

Σ₂P: NP With NP Oracle

Complement of Π₂P.

Along with Π₂P, comprises the second level of PH, the polynomial hierarchy.

[Uma98] has shown that the following problems are complete for Σ₂P:

• Minimum equivalent DNF. Given a DNF formula F and integer k, is there a DNF formula equivalent to F with k or fewer occurences of literals?
• Shortest implicant. Given a formula F and integer k, is there a conjunction of k or fewer literals that implies F? (Note that this problem cannot be Σ₂P-complete for DNF formulas unless Σ₂P equals βP^NP.)

For any fixed k, there is a problem in Σ₂P ∩ Π₂P that cannot be solved by circuits of size n^k [Kan82].

---

SKC: Statistical Knowledge Complexity

A hierarchy of generalizations of SZK, in which Arthur is allowed to gain some information from his interaction with Merlin.

Defined in [GP91].

There are several variants (which we only describe roughly), including:

• SKC_hint(k(n)): Hint sense. The simulator can reproduce Arthur's view of the protocol if given a hint string of size k(n).
• SKC_hint(k(n)): Strict oracle sense. The simulator can reproduce Arthur's view if allowed k(n) queries to an oracle O.
• SKC_avg(k(n)): Average oracle sense. For each input, the expected number of queries the simulator makes to oracle O is at most k(n).
• SKC_ent(k(n)): Entropy sense. Defined in [ABV95]. For each input, the expectation (over Arthur's random coins) of -log(P) is at most k(n), where P is the probability that the view output by the simulator equals the view resulting from the actual protocol.

See also: PKC.

---

SL: Symmetric Logarithmic-Space

The class of problems solvable by a nondeterministic Turing machine in logarithmic space, such that

1. If the answer is 'yes,' one or more computation paths accept.
2. If the answer is 'no,' all paths reject.
3. If the machine can make a nondeterministic transition from configuration A to configuration B, then it can also transition from B to A. (This is what 'symmetric' means.)

Defined in [LP82].

The reachability problem (is there a path from vertex s to vertex t?) for undirected graphs is complete for SL, under L-reduction.

SL contains L, and is contained in NL.

It follows from [AKL+79] that SL is contained in L/poly.

[KW93] showed that SL is contained in ⊕L, as well as Mod_kL for every prime k.

SL is also contained in DSPACE(log^3/2n) [NSW92], and indeed in DSPACE(log^4/3n) [ATW+00].

[NT95] showed that SL equals coSL, and furthermore that SL^SL = SL (that is, the symmetric logspace hierarchy collapses).

The story ends with the remarkable result that SL = L (even relative to an oracle) [Rei04].

---

SLICEWISE PSPACE: Parametrized PSPACE

The parameterized version of PSPACE.

Same as FPT, except that now on input (x,k) (k a parameter), the space used must be f(k)p(|x|), where p is a polynomial.

If P = PSPACE, then FPT = SLICEWISE PSPACE.

Defined in [DF99].

---

SNP: Strict NP

[Fag74] showed that NP is precisely the class of decision problems reducible to a graph-theoretic property expressible in second-order existential logic. For example (see [Pap94]), the property "graph G has a Hamiltonian path" is expressible as

There exists a relation P(u,v) on vertices of G, such that P(u,u) is false, and for all distinct u,v either P(u,v) or P(v,u), and P(u,v) and P(v,w) implies P(u,w), and if P(u,w) and there does not exist a v for which P(u,v) and P(v,w), then there is an edge from u to w.

(Here the relation P(u,v) defines a total order on vertices, such that any two consecutive vertices must be adjacent.)

Then SNP is the class of decision problems reducible to a graph-theoretic predicate with only universal quantifiers over vertices, no existential quantifiers. As an example, k-SAT (CNF satisfiability with at most k literals per clause, for k a constant) is in SNP. But general SAT is not in SNP, basically because we're not allowed to say, "There exists a literal in this clause that satisfies the clause."

See also: MaxSNP.

---

SO-E: Second Order Existential

The class of decision problems for which a "yes" answer is expressible by a proposition with second-order existential quantifiers followed by a first-order formula. See [Imm98] for a full definition.

SO-E = NP [Fag74].

Contains FO(poly(n)).

---

SP: Semi-Efficient Parallel

The class of problems in P for which the best parallel algorithm (using a polynomial number of processors) is faster than the best serial algorithm by a factor of Ω(n^ε) for some ε>0.

Defined in [KRS90].

SP is also an alternate name for XP_uniform

---

span-P: Span Polynomial-Time

The class of functions computable as |S|, where S is the set of output values returned by the accepting paths of an NP machine.

Defined in [KST+89], where it is also shown that span-P contains #P and OptP; and that span-P = #P if and only if UP = NP.

---

SPARSE: Sparse Languages

The class of decision problems for which the number of 'yes' instances of size n is upper-bounded by a polynomial in n. If SPARSE intersects NPC then P = NP [Mah82].

Contains TALLY.

---

SPL: Stoic PL

Has the same relation to PL as SPP does to PP.

Contains the maximum matching and perfect matching problems under a pseudorandom assumption [ARZ99].

Contains UL.

Contained in C₌L and Mod_kL.

Equals the set of problems low for GapL.

---

SPP: Stoic PP

The class of decision problems solvable by an NP machine such that

1. If the answer is "no," then the number of accepting computation paths exactly equals the number of rejecting paths.
2. If the answer is "yes," then these numbers differ by 2.

(A technicality: If the total number of paths is even then the numbers can't differ by 1.)

Defined in [FFK94], where it was also shown that SPP is low for PP, C₌P, Mod_kP, and SPP itself. (I.e. adding SPP as an oracle does not increase the power of these classes.)

Independently defined in [OH93], who called the class XP.

Contained in LWPP, C₌P, and WPP among other classes.

Contains FewP; indeed, FewP is low for SPP, so that SPP^FewP = SPP [FFK94].

Contains the problem of deciding whether a graph has any nontrivial automorphisms [KST92].

Indeed, contains graph isomorphism [AK02].

Contains a whole gaggle of problems for solvable black-box groups: solvability testing, membership testing, subgroup testing, normality testing, order verification, nilpotetence testing, group isomorphism, and group intersection [Vin04]

[AK02] also showed that the Hidden Subgroup Problem for permutation groups, of interest in quantum computing, is in FP^SPP.

---

SQG: Short Quantum Games

Same as QRG, except that now the verifier can exchange only a single round of quantum messages with the two provers. The verifier may process the yes-prover's response before sending a message to the no-prover (compare with RG[1], wherein the verifier's messages must be sent to the provers in parallel).

Defined in [GW05], where it was also shown that SQG contains QIP.

SQG is contained in EXP [Gut05], as well as in QRG.

SQG trivially contains QS₂P.

---

SUBEXP: Deterministic Subexponential-Time

The intersection of DTIME(2^{n^ε}) over all ε>0. (Note that the algorithm used may vary with ε.)

---

symP: Alternate Name for S₂P

---

SZK: Statistical Zero Knowledge

The class of decision problems for which a "yes" answer can be verified by a statistical zero-knowledge proof protocol. In such a protocol, we have a BPP (i.e. probabilistic polynomial-time) verifier, Arthur, and a prover, Merlin, who has unbounded computational resources. By sending messages back and forth with Merlin, Arthur must become convinced (with high probability) that the answer is "yes," without learning anything else about the problem (statistically).

What does that mean? For each choice of random coins, Arthur has a "view" of his entire interaction with Merlin, consisting of his random coins as well as all messages sent back and forth. Then the distribution over views resulting from interaction with Merlin has to be statistically close to a distribution that Arthur could generate himself (in polynomial-time), without interacting with Merlin. (Here "statistically close" means that, say, the trace distance is at most 1/10.)

The most famous example of such a protocol is for graph nonisomorphism. Given two graphs G and H, Arthur can pick one of the graphs (each with probability 1/2), permute its vertices randomly, send the resulting graph to Merlin, and ask, "Which graph did I start with, G or H?" If G and H are non-isomorphic, Merlin can always answer correctly (since he can use exponential time), but if they're isomorphic, he can answer correctly with probability at most 1/2. Thus, if Merlin always gives the correct answer, Arthur becomes convinced the graphs are not isomorphic. On the other hand, Arthur already knew which graph (G or H) he started with, so he could simulate his entire view of the interaction himself, without Merlin's help.

If that sounds like a complicated definition, well, it is. But it turns out that SZK has extremely nice properties. [Oka96] showed that:

• SZK is closed under complement. I.e. Arthur can verify in zero-knowledge that two graphs are isomorphic, not only that they aren't.
• We can assume without loss of generality that the whole interaction consists of a constant number of messages.
• Amazingly, we can also assume without loss of generality that the protocol is public-coin. I.e. Arthur doesn't need to hide any of his random bits, as he did in the graph nonisomorphism protocol above, but can just send them all to Merlin!
• Finally, we can assume without loss of generality that the verifier (Arthur) is honest. A dishonest verifier would be one that tries to learn something about the problem (violating the zero-knowledge requirement) by deviating from the protocol.

Subsequently, [SV97] showed that SZK has a natural complete promise problem, called Statistical Difference (SD). Given two polynomial-size circuits, C₀ and C₁, let D₀ and D₁ be the distributions over their respective outputs when they're given as input a uniformly random n-bit string. We're promised that D₀ and D₁ have trace distance either at most 1/3 or at least 2/3; the problem is to decide which is the case.

Note: The constants 1/3 and 2/3 can be amplified to 2^-poly(n) and 1-2^-poly(n) respectively. But it is crucial that (2/3)² > 1/3.

Another complete promise problem for SZK is Entropy Difference (ED) [GV99]. Here we're promised that either H(D₀)>H(D₁)+1 or H(D₁)>H(D₀)+1, where the distributions D₀ and D₁ are as above, and H denotes Shannon entropy. The problem is to determine which is the case.

If any hard-on-average language is in SZK, then one-way functions exist [Ost91].

Zero-knowledge proofs were first studied in [GMW91], [GMR89].

Contains PZK and NISZK, and is contained in AM ∩ coAM, as well as CZK and QSZK.

There exists an oracle relative to which SZK is not in BQP [Aar02].

Contained in DQP [Aar02b].

---

SZK_h: SZK With Limited Help

The class of decision problems for which a "yes" answer can be verified by a statistical zero-knowledge proof protocol, and the prover and verifier both have access to a string computed by a trusted probabilistic polynomial-time third party with access to the input.

Defined in [BG03], where it was also shown that SZK_h = SZK.

Contains NISZK_h.

---

TALLY: Tally Languages

The class of decision problems for which every 'yes' instance has the form 0ⁿ (i.e. inputs are encoded in unary). If TALLY intersects NPC then P = NP [Mah82].

Contained in SPARSE.

---

TC⁰: Constant-Depth Threshold Circuits

The class of decision problems solvable by polynomial-size, constant-depth circuits with unbounded fanin, which can use AND, OR, and NOT gates (as in AC⁰) as well as threshold gates. A threshold gate returns 1 if at least half of its inputs are 1, and 0 otherwise.

A uniformity requirement is sometimes also placed.

TC⁰ contains ACC⁰, and is contained in NC¹.

TC⁰ circuits of depth 3 are strictly more powerful than TC⁰ circuits of depth 2 [HMP+93].

TC⁰ circuits of depth 3 and quasipolynomial size can simulate all of ACC⁰ [Yao90].

[NR97] give a candidate pseudorandom function family computable in TC⁰, that is secure assuming a subexponential lower bound on the hardness of factoring. (See also [NRR01] for an improvement of this construction, as well as [Kha93].)

One implication is that, assuming such a bound, there is no natural proof in the sense of [RR97] separating TC⁰ from P/poly. (It is important for this that a function family, and not just a candidate pseudorandom generator, is computable in TC⁰.) Another implication is that functions in TC⁰ are likely to be difficult to learn.

The permanent of a 0-1 matrix cannot be computed in uniform TC⁰ [All99].

In a breakthrough result [Hes01] (building on [BCH86] and [CDL01]), integer division was shown to be in L-uniform TC⁰. Indeed division is complete for this class under AC⁰ reductions.

---

TFNP: Total Function NP

The class of function problems of the following form:

Given an input x and a polynomial-time predicate F(x,y), output any y satisfying F(x,y). (Such a y is promised to exist.)

Can be considered as the functional analogue of NP ∩ coNP. Defined in [MP91].

Contained in FNP.

Subclasses include PPA, PPP, and PLS.

---

Θ₂P: Alternate name for P^NP[log]

---

TreeBQP: BQP Restricted To Tree States

The class of languages accepted by a BQP machine subject to the constraint that at every time step t, the machine's state is exponentially close to a tree state -- that is, a state expressible by a polynomial-size tree of additions and tensor products (together with complex constants and |0> and |1> leaf nodes).

More formally, a uniform classical polynomial-time algorithm generates a sequence of gates g⁽¹⁾, ... ,g^(p(n)). Each g^(t) can be either be selected from some finite universal basis of unitary gates (the choice turns out not to matter), or can be a 1-qubit measurement. When we perform a measurement, the state evolves to one of two possible pure states, with the usual probabilities, rather than to a mixed state. We require that the final gate g^(p(n)) is a measurement of the first qubit. If at least one intermediate state was more than distance 2^-Ω(n) away from the nearest state of tree size at most p(n), then the outcome of the final measurement is chosen adversarially; otherwise it is given by the usual Born probabilities. The measurement must return 1 with probability at least 2/3 if the input is in the language, and with probability at most 1/3 otherwise.

Contains BPP, and is contained in BQP.

Defined in [Aar03b], where it was also shown that TreeBQP is contained in the third level of PH, which might provide weak evidence that TreeBQP does not equal BQP.

---

TREE-REGULAR: Regular Tree-Valued Languages

Same as REG, except that now the inputs are trees (say, binary trees) instead of strings. Each vertex is labeled with a symbol from a fixed alphabet. Evaluation begins at the leaves and proceeds to the root. The state of the finite automaton at each vertex v is a function of (1) the states at v's children (if any), and (2) the symbol at v. The tree is in the language if and only if the automaton is in an 'accept' state at the root.

See [Koz92] for example.

---

UAP: Unambiguous Alternating Polynomial-Time

Same as AP, except we are promised that each existential quantifier has at most one 'yes' path, and each universal quantifier has at most one 'no' path.

Contains UP.

Defined in [NR98], where it was also shown that, even though AP = PSPACE, it is unlikely that the same is true for UAP, since UAP is contained in SPP.

[CGR+04] have also shown that UAP^UAP = UAP, and that UAP contains the Graph Isomorphism problem.

---

UCC: Unique Connected Component

The class of problems reducible in L to the problem of whether an undirected graph has a unique connected component.

See [AG00] for more information.

Contained in SL.

See also coUCC.

---

UL: Unambiguous L

Has the same relation to L as UP does to P.

If UL = NL, then FNL is contained in #L [AJ93].

---

UL/poly: Nonuniform UL

Has the same relation to UL as P/poly does to P.

Equals NL/poly [RA00]. (A corollary is that UL/poly is closed under complement).

Note that in UL/poly, the witness must be unique even for bad advice. UL/mpoly (as in BQP/mpoly) is a more natural definition, but this is a moot distinction here because [RA00] show that they both equal NL/poly.

---

UE: Unambiguous Exponential-Time With Linear Exponent

Has the same relation to E as UP does to P.

---

UP: Unambiguous Polynomial-Time

The class of decision problems solvable by an NP machine such that

1. If the answer is 'yes,' exactly one computation path accepts.
2. If the answer is 'no,' all computation paths reject.

"Worst-case" one-way functions exist if and only if P does not equal UP ([GS88] and independently [Ko85]). "Worst-case" one-way permutations exist if and only if P does not equal UP ∩ coUP [HT03]. Note that these are weaker than the one-way functions and permutations that are needed for cryptographic applications.

There exists an oracle relative to which P is strictly contained in UP is strictly contained in NP [Rac82]; indeed, these classes are distinct with probability 1 relative to a random oracle [Bei89].

NP is contained in RP^Promise-UP [VV86]. On the other hand, [BBF98] give an oracle relative to which P = UP but still P does not equal NP.

UP is not known or believed to contain complete problems. [Sip82], [HH86] give oracles relative to which UP has no complete problems.

---

US: Unique Polynomial-Time

The all-American counting class.

The class of decision problems solvable by an NP machine such that the answer is 'yes' if and only if exactly one computation path accepts.

In contrast to UP, a machine can legally have more than one accepting path - that just means that the corresponding input is not in the language.

Defined in [BG82].

Contains coNP.

---

VNC_k: Valiant NC Over Field k

Has the same relation to VP_k as NC does to P.

More formally, the class of VP_k problems computable by a straight-line program of depth polylogarithmic in n.

Surprisingly, VNC_k = VP_k for any k [VSB+83].

---

VNP_k: Valiant NP Over Field k

A superclass of VP_k in Valiant's algebraic complexity theory, but not quite the analogue of NP.

A problem is in VNP_k if there exists a polynomial p with the following properties:

• p is computable in VP_k; that is, by a polynomial-size straight-line program.
• The inputs to p are constants c₁,...,c_m,e₁,...,e_h and indeterminates X₁,...,X_n over the base field k.
• When p is summed over all 2^h possible assignments of {0,1} to each of e₁,...,e_h, the result is some specified polynomial q.

Originated in [Val79b].

If the field k has characteristic greater than 2, then the permanent of an n-by-n matrix of indeterminates is VNP_k-complete under a type of reduction called p-projections ([Val79b]; see also [Bur00]).

A central conjecture is that for all k, VP_k is not equal to VNP_k. Bürgisser [Bur00] shows that if this were false then:

• If k is finite, NC²/poly = P/poly = NP/poly = PH/poly.
• If k has characteristic 0, then assuming the Generalized Riemann Hypothesis (GRH), NC³/poly = P/poly = NP/poly = PH/poly, and #P/poly = FP/poly.

In both cases, PH collapses to Σ₂P.

---

VP_k: Valiant P Over Field k

The class of efficiently-solvable problems in Valiant's algebraic complexity theory.

More formally, the input consists of constants c₁,...,c_m and indeterminates X¹,...,X_n over a base field k (for instance, the complex numbers or Z₂). The desired output is a collection of polynomials over the X_i's. The complexity is the minimum number of pairwise additions, subtractions, and multiplications needed by a straight-line program to produce these polynomials. VP_k is the class of problems whose complexity is polynomial in n. (Hence, VP_k is a nonuniform class, in contrast to P_C and P_R.)

Originated in [Val79b]; see [Bur00] for more information.

Contained in VNP_k and VQP_k, and contains VNC_k.

---

VQP_k: Valiant QP Over Field k

Has the same relation to VP_k as QP does to P.

Originated in [Val79b].

The determinant of an n-by-n matrix of indeterminates is VQP_k-complete under a type of reduction called qp-projections (see [Bur00] for example). It is an open problem whether the determinant is VP_k-complete.

---

W[1]: Weighted Analog of NP

The class of decision problems of the form (x,k) (k a parameter), that are fixed-parameter reducible to the following:

Weighted 3SAT: Given a 3SAT formula, does it have a satisfying assignment of Hamming weight k?

A fixed-parameter reduction is a Turing reduction that takes time at most f(k)p(|x|), where f is an arbitrary function and p is a polynomial. Also, if the input is (x,k), then all Weighted 3SAT instances the algorithm queries about must have the form <x',k'> where k' is at most k.

Contains FPT.

Defined in [DF99], where the following is also shown:

• If FPT = W[1] then NP is contained in DTIME(2^o(n)).

W[1] can be generalized to W[t].

---

WAPP: Weak Almost-Wide PP

The class of decision problems for which there exists a #P function f, a polynomial p, and an ε > 0, such that for all inputs x,

1. If the answer is "yes" then 2^p(|x|) ≥ f(x) > (1+ε) 2^p(|x|)-1.
2. If the answer is "no" then 0 ≤ f(x) < (1-ε) 2^p(|x|)-1.

Defined in [BGM02], where it is also shown that WAPP is contained in AWPP and SBP.

---

W[P]: Weighted Circuit Satisfiability

The class of decision problems of the form (x,k) (k a parameter), that are fixed-parameter reducible to the following problem, for some constant h:

Weighted Circuit-SAT: Given a Boolean circuit C (with no restriction on depth), does C have a satisfying assignment of Hamming weight k?

See W[1] for the definition of fixed-parameter reducibility.

Defined in [DF99].

Contains W[SAT].

---

WPP: Wide PP

The class of decision problems solvable by an NP machine such that

1. If the answer is "no," then the number of accepting computation paths exactly equals the number of rejecting paths.
2. If the answer is "yes," then their difference exactly equals a function f(x) computable in polynomial time (i.e. FP).

Defined in [FFK94].

Contained in C₌P ∩ coC₌P, as well as AWPP.

Contains SPP and LWPP.

---

W[SAT]: Weighted Satisfiability

The class of decision problems of the form (x,k) (k a parameter), that are fixed-parameter reducible to the following problem, for some constant h:

Weighted SAT: Given a Boolean formula F (with no restriction on depth), does F have a satisfying assignment of Hamming weight k?

See W[1] for the definition of fixed-parameter reducibility.

Defined in [DF99].

Contains W[t] for every t, and is contained in W[P].

---

W[*]: Union of W[t]'s

The union of W[t] over all t.

---

W[t]: Nondeterministic Fixed-Parameter Hierarchy

A generalization of W[1].

The class of decision problems of the form (x,k) (k a parameter), that are fixed-parameter reducible to the following problem, for some constant h:

Weighted Weft-t Depth-h Circuit-SAT: Given a Boolean circuit C, with a mixture of fanin-2 and unbounded-fanin gates. The number unbounded-fanin gates along any path to the root is at most t, and the total depth (fanin-2 and unbounded-fanin) is at most h. Does C have a satisfying assignment of Hamming weight k?

See W[1] for the definition of fixed-parameter reducibility.

Defined in [DF99].

Contained in W[SAT] and in W^*[t].

---

W^*[t]: W[t] With Parameter-Dependent Depth

Same as W[t], except that now the circuit depth can depend on the parameter k rather than being constant. (The number of unbounded-fanin gates along any path to the root is still at most t.)

W^*[1] = W[1] [DFT96], and W^*[2] = W[2] [DF97], but the problem is open for larger t.

---

XOR-MIP*[2,1]: MIP*[2,1] With 1-Bit Proofs

Same as MIP*[2,1], but with the further restriction that both provers send only a single bit to the verifier, and the verifier's output is a function of the exclusive-OR of those bits. There should exist 0<a<b<1 such that if the answer is "yes", then for some responses of the provers the verifier accepts with probability at least b, while if the answer is "no", then for all responses of the provers the verifier accepts with probability at most a.

Defined by [CHT+04], whose motivation was a connection to the Bell and CHSH inequalities of quantum physics.

XOR-MIP*[2,1] is contained in NEXP [CHT+04].

---

XP: Fixed-Parameter Tractable for Each Parameter

The class of decision problems of the form (x,k) (k a parameter) that are solvable in time O(|x|^f(k)) for some function f. The algorithm used may depend on k.

Defined in [DF99].

Contains XP_uniform.

Strictly contains FPT (by diagonalization).

---

XP_uniform: Uniform XP

Same as XP except that the algorithm used must be the same for each k (though it can take k as input).

Defined in [DF99].

---

YACC: Yet Another Complexity Class

A term of derision, used against a complexity class.

---

YP: Your Polynomial-Time or Yaroslav-Percival

The class of decision problems for which there exists a polynomial-time machine M such that:

• For all input sizes n, there exists a polynomial-size advice string s_n such that M(x,s_n) outputs the correct answer for all inputs x of size n.
• For all inputs x and advice strings s, M(x,s) outputs either the correct answer or "I don't know."

Defined in a recent post of the blog Shtetl-Optimized. See there for an explanation of the class's name.

Contains ZPP by the same argument that places BPP in P/poly.

Also contains P with TALLY ∩ NP ∩ coNP oracle.

Is contained in NP ∩ coNP and YPP.

---

YPP: Yaroslav BPP

The probabilistic analogue of YP; it is to YP what MA is to NP. Formally, the class of decision problems for which there exists a syntactic BPP machine M such that:

• For all input sizes n, there exists a polynomial-size advice string a_n such that for all inputs x of size n, M(x,a_n) outputs the correct answer with probability at least 2/3.
• For all inputs x and advice strings a, the probability that M(x,a) outputs the incorrect answer is at most 1/3. In other words, the sum of the probabilities of the correct answer and "I don't know" is at least 2/3.

To amplify a YPP machine, one can run it multiple times, then accept if a majority of runs accept, reject if a majority reject, and otherwise output "I don't know."

Contains BPP and YP, and is contained in MA and P/poly.

---

YQP: Yaroslav BQP

Is to YPP as BQP is to BPP, and QMA is to MA. The machine is now a quantum computer and the advice is a quantum state |ψ_n>.

Contains BQP and YPP, and is contained in QMA and BQP/qpoly.

---

ZBQP: Strict Quantum ZPP

Defined as RBQP ∩ coRBQP. Equivalently, the class of problems in NP ∩ coNP such that both positive and negative witnesses are in FBQP.

For example, the language of square-free numbers is in ZBQP, because factoring is in FBQP and a factorization can be certified in ZPP (indeed in P, by [AKS02]).

Unlike EQP or ZQP, ZBQP would generalize ZPP in practice if quantum computers existed, in the sense that it provides proven answers.

Contains ZPP and is contained in RBQP and ZQP. Also, ZBQP^ZBQP = ZBQP. Defined here to clarify EQP and ZQP.

---

ZPE: Zero-Error Probabilistic E

Same as ZPP, but with 2^O(n)-time instead of polynomial-time.

ZPE = EE if and only if ZPP = EXP [IKW01].

---

ZPP: Zero-Error Probabilistic Polynomial-Time

Defined as RP ∩ coRP.

The class of problems solvable by randomized algorithms that always return the correct answer, and whose expected running time (on any input) is polynomial.

Defined in [Gil77].

Contains the problem of testing whether an integer is prime [SS77] [AH87].

In contrast to BPP and RP, it is not known whether showing ZPP = P requires proving superpolynomial circuit lower bounds [KI02].

There exists an oracle relative to which ZPP = EXP [Hel84].

---

ZPTIME(f(n)): Zero-Error Probabilistic f(n)-Time

Same as ZPP, but with O(f(n))-time instead of polynomial-time.

For any constructible superpolynomial f, ZPTIME(f(n)) with NP oracle is not contained in P/poly [KW98].

---

ZQP: Zero-Error Extension Of EQP

The class of questions that can be answered by a QTM that answers yes, no, or "maybe". If the correct answer is yes, then P[no] = 0, and vice-versa; and the probability of maybe is at most 1/2. Since some of the probabilities have to vanish, ZQP has the same technical caveats as EQP.

Defined independently in [BW03] and in [Nis02].

Contains EQP and ZBQP and is contained in BQP. Equals RQP ∩ coRQP. There is an oracle such that ZQP^ZQP is larger than ZQP [BW03]; c.f. with ZBQP.

---