https://complexityzoo.net/api.php?action=feedcontributions&user=Atn&feedformat=atomComplexity Zoo - User contributions [en]2021-09-26T06:48:44ZUser contributionsMediaWiki 1.35.0https://complexityzoo.net/index.php?title=Complexity_Zoo:A&diff=6664Complexity Zoo:A2020-06-17T13:20:45Z<p>Atn: /* AM: Arthur-Merlin */</p>
<hr />
<div>__NOTOC__<br />
{{CZ-Letter-Menu|A}}<br />
<br />
<br />
===== <span id="a0pp" style="color:red">A<sub>0</sub>PP</span>: One-Sided Analog of [[#awpp|AWPP]] =====<br />
Same as [[Complexity Zoo:S#sbp|SBP]], except that f is a nonnegative-valued [[Complexity Zoo:G#gapp|GapP]] function rather than a [[Complexity Zoo:Symbols#sharpp|#P]] function.<br />
<br />
Defined in [[zooref#vya03|[Vya03]]], where the following was also shown:<br />
<ul><br />
<li>A<sub>0</sub>PP contains [[Complexity Zoo:Q#qma|QMA]], [[#awpp|AWPP]], and [[Complexity Zoo:C#cocequalsp|coC<sub>=</sub>P]].</li><br />
<li>A<sub>0</sub>PP is contained in [[Complexity Zoo:P#pp|PP]].</li><br />
<li>If A<sub>0</sub>PP = [[Complexity Zoo:P#pp|PP]] then [[Complexity Zoo:P#ph|PH]] is contained in [[Complexity Zoo:P#pp|PP]].</li><br />
</ul><br />
<br />
Kuperberg ([[zooref#kup09|[Kup09]]]) showed that A<sub>0</sub>PP = [[Complexity Zoo:S#sbqp|SBQP]].<br />
----<br />
<br />
===== <span id="ac" style="color:red">AC</span>: Unbounded Fanin Polylogarithmic-Depth Circuits =====<br />
AC<sup>i</sup> is the class of decision problems solvable by a nonuniform family of Boolean circuits, with polynomial size, depth O(log<sup>i</sup>(n)), and unbounded fanin. The gates allowed are AND, OR, and NOT.<br />
<br />
Then AC is the union of AC<sup>i</sup> over all nonnegative i.<br />
<br />
AC<sup>i</sup> is contained in [[Complexity Zoo:N#nc|NC]]<sup>i+1</sup>; thus, AC = [[Complexity Zoo:N#nc|NC]].<br />
<br />
Contains [[Complexity Zoo:N#nl|NL]].<br />
<br />
For a random oracle A, (AC<sup>i</sup>)<sup>A</sup> is strictly contained in (AC<sup>i+1</sup>)<sup>A</sup>, and (uniform) AC<sup>A</sup> is strictly contained in P<sup>A</sup>, with probability 1 [[zooref#mil92|[Mil92]]].<br />
<br />
fo-uniform AC with depth <math>t(n)</math> is equal to [[#Complexity_Zoo:F#fot|FO[<math>t(n)</math>]]]<br />
----<br />
<br />
===== <span id="ac0" style="color:red">AC<sup>0</sup></span>: Unbounded Fanin Constant-Depth Circuits =====<br />
An especially important subclass of [[#ac|AC]], corresponding to constant-depth, unbounded-fanin, polynomial-size circuits with AND, OR, and NOT gates.<br />
<br />
Computing the [[Complexity_Garden#parity|Parity]] or [[Complexity_Garden#majority|Majority]] of n bits is not in AC<sup>0</sup> [[zooref#fss84|[FSS84]]].<br />
<br />
There are functions in AC<sup>0</sup> that are pseudorandom for all statistical tests in AC<sup>0</sup> [[zooref#nw94|[NW94]]]. But there are no functions in AC<sup>0</sup> that are pseudorandom for all statistical tests in [[Complexity Zoo:Q#qp|QP]] (quasipolynomial time) [[zooref#lmn93|[LMN93]]].<br />
<br />
[[zooref#lmn93|[LMN93]]] showed furthermore that functions with AC<sup>0</sup> circuits of depth d are learnable in [[#qp|QP]], given their outputs on O(2<sup>log(n)^O(d)</sup>) randomly chosen inputs. On the other hand, this learning algorithm is essentially optimal, unless there is a 2<sup>n^o(1)</sup> algorithm for [[Complexity_Garden#integer_factorization|factoring]] [[zooref#kha93|[Kha93]]].<br />
<br />
Although there are no good pseudorandom <i>functions</i> in AC<sup>0</sup>, [[zooref#in96|[IN96]]] showed that there are pseudorandom <i>generators</i> that stretch n bits to n+&#920;(log n), assuming the hardness of a problem based on subset sum.<br />
<br />
AC<sup>0</sup> contains [[Complexity Zoo:N#nc0|NC<sup>0</sup>]], and is contained in [[Complexity Zoo:Q#qacf0|QAC<sub>f</sub><sup>0</sup>]] and [[Complexity Zoo:M#mac0|MAC<sup>0</sup>]].<br />
<br />
In descriptive complexity, uniform AC<sup>0</sup> 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 [[zooref#lee02|[Lee02]]]). So it's equivalent to the class [[Complexity_Zoo:F#fo|FO]], and to the alternating logtime hierarchy.<br />
<br />
[[zooref#blm98|[BLM+98]]] showed the following problem is complete for depth-k AC<sup>0</sup> circuits (with a uniformity condition):<br />
<ul> 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). </ul><br />
<br />
----<br />
<br />
===== <span id="ac0m" style="color:red">AC<sup>0</sup>[m]</span>: [[#ac0|AC<sup>0</sup>]] With MOD m Gates =====<br />
Same as [[#ac0|AC<sup>0</sup>]], 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.)<br />
<br />
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<sup>0</sup>[m] [[zooref#raz87|[Raz87]]] [[zooref#smo87|[Smo87]]]. It follows that, for any such m, AC<sup>0</sup>[m] is strictly contained in [[Complexity Zoo:N#nc1|NC<sup>1</sup>]].<br />
<br />
However, if m is a product of distinct primes (e.g. 6), then it is not even known whether AC<sup>0</sup>[m] = [[Complexity Zoo:N#np|NP]]!<br />
<br />
See also: [[Complexity Zoo:Q#qac0m|QAC<sup>0</sup>[m]]].<br />
<br />
----<br />
<br />
===== <span id="ac1" style="color:red">AC<sup>1</sup></span>: Unbounded Fanin Log-Depth Circuits =====<br />
See [[#ac|AC]].<br />
<br />
----<br />
===== <span id="acc0" style="color:red">ACC<sup>0</sup></span>: [[#ac0|AC<sup>0</sup>]] With Arbitrary MOD Gates =====<br />
Same as [[#ac0m|AC<sup>0</sup>[m]]], but now the constant-depth circuit can contain MOD m gates for <i>any</i> m.<br />
<br />
Contained in [[Complexity Zoo:T#tc0|TC<sup>0</sup>]].<br />
<br />
Indeed, can be simulated by depth-3 threshold circuits of quasipolynomial size [[zooref#yao90|[Yao90]]].<br />
<br />
According to [[zooref#all96|[All96]]], there is no good evidence for the existence of cryptographically secure functions in ACC<sup>0</sup>. <br />
<br />
There is no non-uniform ACC<sup>0</sup> circuits of polynomial size for [[Complexity Zoo:R#N:ntime|NTIMES[2<sup>n</sup>]]] and no ACC<sup>0</sup> circuit of size 2<sup>n<sup>O(1)</sup></sup> for E<sup>NP</sup> (The class [[Complexity Zoo:E#e|E]] with an [[Complexity Zoo:N#np|NP]] oracle). These are the only two known nontrivial lower bounds against ACC<sup>0</sup> and were recently discovered by [[zooref#wil11|[Wil11]]]. <br />
<br />
Contains 4-[[Complexity Zoo:P#kpbp|PBP]] [[zooref#bt88|[BT88]]].<br />
<br />
See also: [[Complexity Zoo:Q#qacc0|QACC<sup>0</sup>]].<br />
<br />
----<br />
<br />
===== <span id="ah" style="color:red">AH</span>: Arithmetic Hierarchy =====<br />
The analog of [[Complexity Zoo:P#ph|PH]] in computability theory.<br />
<br />
Let &#916;<sub>0</sub> = &#931;<sub>0</sub> = &#928;<sub>0</sub> = [[Complexity Zoo:R#r|R]]. Then for i&gt;0, let<br />
<ul><br />
<li>&#916;<sub>i</sub> = [[Complexity Zoo:R#r|R]] with &#931;<sub>i-1</sub> oracle.</li><br />
<li>&#931;<sub>i</sub> = [[Complexity Zoo:R#re|RE]] with &#931;<sub>i-1</sub> oracle.</li><br />
<li>&#928;<sub>i</sub> = [[Complexity Zoo:C#core|coRE]] with &#931;<sub>i-1</sub> oracle.</li><br />
</ul><br />
Then AH is the union of these classes for all nonnegative constant i.<br />
<br />
Each level of AH strictly contains the levels below it.<br />
<br />
An equivalent definition is: <math>\Sigma_0=\Delta_0=\Pi_0</math> is the set of numbers decided by formula with one free variable and bounded quantifier, where the primitives are + and <math>\times</math>. A bounded quantifier is of the form <math> \phi=\forall i<j \psi </math> or <math>\phi=\exists i<j \psi</math> where <math>j</math> is considered to be free in <math>\phi</math>. Then <math>\Sigma_{i+1}</math> is the sets of number validating a formula of the form <math>\exists X_1\dots\exists X_n,\psi</math> with <math>\psi\in\Delta_i</math>. <math>\Pi_i</math> is the set of formula who are negation of <math>\Sigma_i</math> formula. <math>\Delta_i=\Sigma_i\cap\Pi_i</math> <br />
----<br />
<br />
===== <span id="al" style="color:red">AL</span>: Alternating [[Complexity_Zoo:L#l|L]] =====<br />
Same as [[#ap|AP]], but for logarithmic-space instead of polynomial-time.<br />
<br />
AL = [[Complexity Zoo:P#p|P]] [[zooref#cks81|[CKS81]]].<br />
<br />
----<br />
<br />
===== <span id="all" style="color:red">ALL</span>: The Class of All Languages =====<br />
Literally, the class of ALL languages.<br />
<br />
ALL is a gargantuan beast that's been wreaking havoc in the Zoo of late.<br />
<br />
First [[zooref#aar04b|[Aar04b]]] observed that [[Complexity Zoo:P#pp|PP]]/rpoly ([[Complexity Zoo:P#pp|PP]] with polynomial-size randomized advice) equals ALL, as does [[Complexity Zoo:P#postbqp|PostBQP]]/qpoly ([[Complexity Zoo:P#postbqp|PostBQP]] with polynomial-size quantum advice).<br />
<br />
Then [[zooref#raz05|[Raz05]]] showed that [[Complexity Zoo:Q#qip|QIP]]/qpoly, and even [[Complexity Zoo:I#ip|IP]](2)/rpoly, equal ALL.<br />
<br />
Nor is it hard to show that [[Complexity Zoo:M#maexp|MA<sub>EXP</sub>]]/rpoly = ALL.<br />
<br />
Also, per [[zooref#aar18|[Aar18]]], [[Complexity Zoo:P#pdqp|PDQP]]/qpoly = ALL.<br />
<br />
On the other hand, even though [[Complexity Zoo:P#pspace|PSPACE]] contains [[Complexity Zoo:P#pp|PP]], and [[Complexity Zoo:E#expspace|EXPSPACE]] contains [[#maexp|MA<sub>EXP</sub>]], it's easy to see that [[Complexity Zoo:P#pspace|PSPACE]]/rpoly = [[Complexity Zoo:P#pspace|PSPACE]]/poly and [[Complexity Zoo:E#expspace|EXPSPACE]]/rpoly = [[Complexity Zoo:E#expspace|EXPSPACE]]/poly are not ALL.<br />
<br />
So does ALL have no respect for complexity class inclusions at ALL? (Sorry.)<br />
<br />
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, [[Complexity Zoo:M#maexp|MA<sub>EXP</sub>]]/rpoly means M(A<sub>EXP</sub>/rpoly), while ([[Complexity Zoo:M#maexp|MA<sub>EXP</sub>]])/rpoly equals [[Complexity Zoo:M#maexp|MA<sub>EXP</sub>]]/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.<br />
<br />
----<br />
<br />
===== <span id="alogtime" style="color:red">ALOGTIME</span>: Logarithmic time alternating RAM =====<br />
<br />
ALOGTIME is the class of languages decidable in logarithmic time by a random access alternating Turing machine.<br />
<br />
Known to be equal to U<sub>E<sup>*</sup></sub>-uniform [[Complexity Zoo:N#nc1|NC<sup>1</sup>]].<br />
<br />
----<br />
<br />
===== <span id="algppoly" style="color:red">AlgP/poly</span>: Polynomial-Size Algebraic Circuits =====<br />
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.<br />
<br />
Named in [[zooref#imp02|[Imp02]]], though it has been considered since the 1970's.<br />
<br />
If [[Complexity Zoo:P#p|P]] = [[Complexity Zoo:B#bpp|BPP]] (or even [[Complexity Zoo:B#bpp|BPP]] is contained in [[Complexity Zoo:N#ne|NE]]), then either [[Complexity Zoo:N#nexp|NEXP]] is not in [[Complexity Zoo:P#ppoly|P/poly]], or else the permanent polynomial of a matrix is not in AlgP/poly [[zooref#ki02|[KI02]]].<br />
<br />
----<br />
===== <span id="almostnp" style="color:red">Almost-[[Complexity Zoo:N#np|NP]]</span>: Languages Almost Surely in [[Complexity Zoo:N#np|NP]]<sup>A</sup> =====<br />
The class of problems that are in [[Complexity Zoo:N#np|NP]]<sup>A</sup> with probability 1, where A is an oracle chosen uniformly at random.<br />
<br />
Equals [[#am|AM]] [[zooref#nw94|[NW94]]].<br />
<br />
----<br />
===== <span id="almostp" style="color:red">Almost-[[Complexity Zoo:P#p|P]]</span>: Languages Almost Surely in [[Complexity Zoo:P#p|P]]<sup>A</sup> =====<br />
The class of problems that are in [[Complexity Zoo:P#p|P]]<sup>A</sup> with probability 1, where A is an oracle chosen uniformly at random.<br />
<br />
Equals [[Complexity Zoo:B#bpp|BPP]] [[zooref#bg81|[BG81]]].<br />
<br />
----<br />
===== <span id="almostpspace" style="color:red">Almost-[[Complexity Zoo:P#pspace|PSPACE]]</span>: Languages Almost Surely in [[Complexity Zoo:P#pspace|PSPACE]]<sup>A</sup> =====<br />
The class of problems that are in [[Complexity Zoo:P#pspace|PSPACE]]<sup>A</sup> with probability 1, where A is an oracle chosen uniformly at random.<br />
<br />
Almost-PSPACE is not known to equal [[Complexity Zoo:P#pspace|PSPACE]] -- rather surprisingly, given the fact that [[Complexity Zoo:P#pspace|PSPACE]] equals BPPSPACE and even [[Complexity Zoo:P#ppspace|PPSPACE]].<br />
<br />
What's known is that Almost-PSPACE = BP<sup>exp</sup>&#149;[[Complexity Zoo:P#pspace|PSPACE]], where [[Zoo Operators#bpexp|BP<sup>exp</sup>&#149;]] is like the [[Zoo Operators#bp|BP&#149;]] operator but with exponentially-long strings [[zooref#bvw98|[BVW98]]]. It follows that Almost-PSPACE is contained in [[Complexity Zoo:N#nexp|NEXP]]<sup>[[Complexity Zoo:N#np|NP]]</sup> &#8745; [[Complexity Zoo:A#conexp|coNEXP]]<sup>[[Complexity Zoo:N#np|NP]]</sup>.<br />
<br />
Whereas both BP<sup>exp</sup>&#149;[[Complexity Zoo:P#pspace|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.<br />
<br />
----<br />
<br />
===== <span id="am" style="color:red">AM</span>: Arthur-Merlin =====<br />
The class of decision problems for which a "yes" answer can be verified by an <i>Arthur-Merlin protocol</i>, as follows.<br />
<br />
Arthur, a [[Complexity Zoo:B#bpp|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<br />
<ol><br />
<li>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).</li><br />
<li>If the answer is "no," then however Merlin acts, Arthur will reject with probability at least 2/3.</li><br />
</ol><br />
Surprisingly, it turns out that such a system is just as powerful as a <i>private-coin</i> one, in which Arthur does not need to send his random coins to Merlin [[zooref#gs86|[GS86]]]. So, Arthur never needs to hide information from Merlin.<br />
<br />
Furthermore, define AM[k] similarly to AM, except that Arthur and Merlin have k rounds of interaction. Then for all constant k&gt;2, AM[k] = AM[2] = AM [[zooref#bm88|[BM88]]]. Also, the result of [[zooref#gs86|[GS86]]] can then be stated as follows: [[Complexity Zoo:I#ip|IP]][k] is contained in AM[k+2] for every k (constant or non-constant).<br />
<br />
AM contains [[Complexity_Garden#graph_isomorphism|graph nonisomorphism]].<br />
<br />
Contains [[Complexity Zoo:N#np|NP]], [[Complexity Zoo:B#bpp|BPP]], and [[Complexity Zoo:S#szk|SZK]], and is contained in [[Complexity Zoo:N#nppoly|NP/poly]].<br />
AM is also contained in [[Complexity Zoo:P#pi2p|&#928;<sub>2</sub>P]] and this proof relativizes so the containment holds relative to any oracle.<br />
<br />
If AM contains [[Complexity Zoo:C#conp|coNP]] then [[Complexity Zoo:P#ph|PH]] collapses to [[Complexity Zoo:S#sigma2p|&#931;<sub>2</sub>P]] &#8745; [[Complexity Zoo:P#pi2p|&#928;<sub>2</sub>P]] [[zooref#bhz87|[BHZ87]]].<br />
<br />
There exists an oracle relative to which AM is not contained in [[Complexity Zoo:P#pp|PP]] [[zooref#ver92|[Ver92]]].<br />
<br />
AM = [[Complexity Zoo:N#np|NP]] under a strong derandomization assumption: namely that some language in [[Complexity Zoo:N#ne|NE]] &#8745; [[Complexity Zoo:C#cone|coNE]] requires nondeterministic circuits of size 2<sup>&#937;(n)</sup> ([[zooref#mv99|[MV99]]], improving [[zooref#km99|[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.)<br />
<br />
----<br />
<br />
===== <span id="amcc" style="color:red">AM<sup>cc</sup></span>: Communication Complexity [[#am|AM]] =====<br />
<br />
Here, Alice and Bob collectively constitute "Arthur", and Merlin sends a message that depends on the input and all the randomness, and the cost is defined to be the bit length of Merlin's message plus the communication cost of the ensuing verification protocol between Alice and Bob. (Without loss of generality, the verification protocol consists only of checking containment in a rectangle, since Merlin could always include the transcript of the verification in his message.)<br />
<br />
It is open to prove that there exists an explicit two-party function that is not in AM<sup>cc</sup>.<br />
<br />
Contained in [[Complexity Zoo:P#phcc|PH<sup>cc</sup>]].<br />
<br />
AM<sup>cc</sup> &#8745; coAM<sup>cc</sup> is not contained in [[Complexity Zoo:P#ppcc|PP<sup>cc</sup>]] if partial functions are allowed [[zooref#kla11|[Kla11]]].<br />
<br />
----<br />
<br />
===== <span id="amexp" style="color:red">AM<sub>EXP</sub></span>: Exponential-Time [[#am|AM]] =====<br />
Same as [[#am|AM]], except that Arthur is exponential-time and can exchange exponentially long messages with Merlin.<br />
<br />
Contains [[Complexity Zoo:M#maexp|MA<sub>EXP</sub>]], and is contained in [[Complexity Zoo:E#eh|EH]] and indeed [[Complexity Zoo:S#s2exppnp|S<sub>2</sub>-EXP&#149;P<sup>NP</sup>]].<br />
<br />
If [[Complexity Zoo:C#conp|coNP]] is contained in [[#ampolylog|AM[polylog]]] then [[Complexity Zoo:E#eh|EH]] collapses to AM<sub>EXP</sub> [[zooref#pv04|[PV04]]].<br />
<br />
----<br />
===== <span id="amicoam" style="color:red">AM &#8745; coAM</span> =====<br />
The class of decision problems for which both "yes" and "no" answers can be verified by an [[#am|AM]] protocol.<br />
<br />
If [[Complexity Zoo:E#exp|EXP]] requires exponential time even for [[#am|AM]] protocols, then AM &#8745; coAM = [[Complexity Zoo:N#npiconp|NP &#8745; coNP]] [[zooref#gst03|[GST03]]].<br />
<br />
There exists an oracle relative to which AM &#8745; coAM is not contained in [[Complexity Zoo:P#pp|PP]] [[zooref#ver95|[Ver95]]].<br />
<br />
----<br />
===== <span id="ampolylog" style="color:red">AM[polylog]</span>: [[#am|AM]] With Polylog Rounds =====<br />
Same as [[#am|AM]], except that we allow polylog(n) rounds of interaction between Arthur and Merlin instead of a constant number.<br />
<br />
Not much is known about AM[polylog] -- for example, whether it sits in [[Complexity Zoo:P#ph|PH]]. However, [[zooref#ss04|[SS04]]] show that if AM[polylog] contains [[Complexity Zoo:C#conp|coNP]], then [[Complexity Zoo:E#eh|EH]] collapses to [[Complexity Zoo:S#s2exppnp|S<sub>2</sub>-EXP&#149;P<sup>NP</sup>]]. ([[zooref#pv04|[PV04]]] improved the collapse to [[#amexp|AM<sub>EXP</sub>]].)<br />
<br />
----<br />
===== <span id="ampmp" style="color:red">AmpMP</span>: Amplifiable [[Complexity Zoo:M#mp2|MP]] =====<br />
The class of decision problems such that for some [[Complexity Zoo:Symbols#sharpp|#P]] function f(x,0<sup>m</sup>),<br />
<ol><br />
<li>The answer on input x is 'yes' if and only if the middle bit of f(x) is 1.</li><br />
<li>The m bits of f(x) to the left and right of the middle bit are all 0.</li><br />
</ol><br />
Defined in [[zooref#gkr95|[GKR+95]]].<br />
<br />
Contains [[Complexity Zoo:P#ph|PH]] and Contained in [[Complexity Zoo:M#mp2|MP]].<br />
<br />
----<br />
===== <span id="amppbqp" style="color:red">AmpP-BQP</span>: [[Complexity Zoo:B#bqp|BQP]] Restricted To [[Zoo_Exhibit#ampp|AmpP]] States =====<br />
Similar to [[Complexity Zoo:T#treebqp|TreeBQP]] except that the quantum computer's state at each time step is restricted to being exponentially close to a state in [[Zoo_Exhibit#ampp|AmpP]] (that is, a state for which the amplitudes are computable by a classical polynomial-size circuit).<br />
<br />
Defined in [[zooref#aar03b|[Aar03b]]], where it was also observed that AmpP-BQP is contained in the third level of [[Complexity Zoo:P#ph|PH]], just as [[Complexity Zoo:T#treebqp|TreeBQP]] is.<br />
<br />
----<br />
===== <span id="ap" style="color:red">AP</span>: Alternating [[Complexity Zoo:P#p|P]] =====<br />
An <i>alternating Turing machine</i> 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.)<br />
<br />
Then AP is the class of decision problems solvable in polynomial time by an alternating Turing machine.<br />
<br />
AP = [[Complexity Zoo:P#pspace|PSPACE]] [[zooref#cks81|[CKS81]]].<br />
<br />
The abbreviation AP is also used for Approximable in Polynomial Time, see [[#axp|AxP]].<br />
<br />
----<br />
===== <span id="app" style="color:red">APP</span>: Amplified [[Complexity Zoo:P#pp|PP]] =====<br />
Roughly, the class of decision problems for which the following holds. For all polynomials p(n), there exist [[Complexity Zoo:G#gapp|GapP]] functions f and g such that for all inputs x with n=|x|,<br />
<ol><br />
<li>If the answer is "yes" then 1 &gt; f(x)/g(1<sup>n</sup>) &gt; 1-2<sup>-p(n)</sup>.</li><br />
<li>If the answer is "no" then 0 &lt; f(x)/g(1<sup>n</sup>) &lt; 2<sup>-p(n)</sup>.</li><br />
</ol><br />
Defined in [[zooref#li93|[Li93]]], where the following was also shown:<br />
<ul><br />
<li>APP is contained in [[Complexity Zoo:P#pp|PP]], and indeed is low for [[Complexity Zoo:P#pp|PP]].</li><br />
<li>APP is closed under intersection, union, and complement.</li><br />
</ul><br />
APP contains [[#awpp|AWPP]] [[zooref#fen02|[Fen02]]].<br />
<br />
The abbreviation APP is also used for Approximable in Probabilistic Polynomial Time, see [[#axpp|AxPP]].<br />
<br />
----<br />
<br />
===== <span id="apx" style="color:red">APX</span>: Approximable =====<br />
The subclass of [[Complexity Zoo:N#npo|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.)<br />
<br />
Contains [[Complexity Zoo:P#ptas|PTAS]].<br />
<br />
Equals the closure of [[Complexity Zoo:M#maxsnp|MaxSNP]] and of [[Complexity Zoo:M#maxnp|MaxNP]] under [[Complexity Zoo:P#ptas|PTAS]] reduction [[zooref#kms99|[KMS+99]]], [[zooref#ct94|[CT94]]].<br />
<br />
Defined in [[zooref#acg99|[ACG+99]]].<br />
<br />
----<br />
===== <span id="atime" style="color: red">ATIME</span>: Alternating [[Complexity Zoo:D#dtime|TIME]] =====<br />
'''ATIME'''(f(n)) is the class of problems for which there are alternating Turing machines (see [[#ap|AP]]) which decide the problem in time bounded by f(n).<br />
<br />
In particular, [[#ap|AP]] = ATIME(poly(n)).<br />
<br />
----<br />
<br />
===== <span id="aucspace" style="color:red">AUC-SPACE(f(n))</span>: Randomized Alternating f(n)-Space =====<br />
The class of problems decidable by an O(f(n))-space Turing machine with three kinds of quantifiers: existential, universal, and randomized.<br />
<br />
Contains [[Complexity Zoo:G#ganspace|GAN-SPACE(f(n))]].<br />
<br />
AUC-SPACE(poly(n)) = [[Complexity Zoo:S#saptime|SAPTIME]] = [[Complexity Zoo:P#pspace|PSPACE]] [[zooref#pap83|[Pap83]]].<br />
<br />
[[zooref#con92|[Con92]]] shows that AUC-SPACE(log n) has a natural complete problem, and is contained in [[Complexity Zoo:N#npiconp|NP &#8745; coNP]].<br />
<br />
----<br />
===== <span id="auxpda" style="color:red">AuxPDA</span>: Auxiliary Pushdown Automata =====<br />
Equivalent to [[Complexity Zoo:N#nauxpdap|NAuxPDA<sup>p</sup>]] without the running-time restriction.<br />
<br />
Equals [[Complexity Zoo:P#p|P]] [[zooref#coo71b|[Coo71b]]].<br />
<br />
----<br />
===== <span id="avbpp" style="color:red">AVBPP</span>: Average-Case [[Complexity Zoo:B#bpp|BPP]] =====<br />
Defined in [[zooref#ow93|[OW93]]] to be the class of decision problems that have a good average-case [[Complexity Zoo:B#bpp|BPP]] algorithm, whenever the input is chosen from an efficiently samplable distribution.<br />
<br />
Note that this is <i>not</i> the same as the [[Complexity Zoo:B#bpp|BPP]] version of [[#avgp|AvgP]].<br />
<br />
----<br />
===== <span id="avge" style="color:red">AvgE</span>: Average Exponential-Time With Linear Exponent =====<br />
Has the same relation to [[Complexity Zoo:E#e|E]] as [[#avgp|AvgP]] does to [[Complexity Zoo:P#p|P]].<br />
<br />
----<br />
===== <span id="avgp" style="color:red">AvgP</span>: Average Polynomial-Time =====<br />
A <i>distributional problem</i> consists of a decision problem A, and a probability distribution &#956; over problem instances.<br />
<br />
A function f, from strings to integers, is <i>polynomial on &#956;-average</i> if there exists a constant &#949;&gt;0 such that the expectation of f<sup>&#949;</sup>(x) is finite, when x is drawn from &#956;.<br />
<br />
Then (A,&#956;) is in AvgP if there is an algorithm for A whose running time is polynomial on &#956;-average.<br />
<br />
This convoluted definition is due to Levin [[zooref#lev86|[Lev86]]], who realized that simpler definitions lead to classes that fail to satisfy basic closure properties. Also see [[zooref#gol97|[Gol97]]] for more information.<br />
<br />
If AvgP = [[Complexity Zoo:D#distnp|DistNP]] then [[Complexity Zoo:E#exp|EXP]] = [[Complexity Zoo:N#nexp|NEXP]] [[zooref#bcg92|[BCG+92]]].<br />
<br />
Strictly contained in [[Complexity Zoo:H#heurp|HeurP]] [[zooref#ns05|[NS05]]].<br />
<br />
See also: [[Complexity Zoo:N#nppsamp|(NP,P-samplable)]].<br />
<br />
----<br />
<br />
===== <span id="awp" style="color:red">AW[P]</span>: Alternating [[Complexity Zoo:W#wp|W[P]]] =====<br />
Same as [[#awsat|AW[SAT]]] but with 'circuit' instead of 'formula.'<br />
<br />
Has the same relation to [[#awsat|AW[SAT]]] as [[Complexity Zoo:W#wp|W[P]]] has to [[Complexity Zoo:W#wsat|W[SAT]]].<br />
<br />
Defined in [[zooref#df99|[DF99]]].<br />
<br />
----<br />
===== <span id="awpp" style="color:red">AWPP</span>: Almost [[Complexity Zoo:W#wpp|WPP]] =====<br />
The class of decision problems solvable by an [[Complexity Zoo:N#np|NP]] machine such that for some polynomial-time computable (i.e. [[Complexity Zoo:F#fp|FP]]) function f,<br />
<ol><br />
<li>If the answer is "no," then the difference between the number of accepting and rejecting paths is non-negative and at most 2<sup>-poly(n)</sup>f(x).</li><br />
<li>If the answer is "yes," then the difference is between (1-2<sup>-poly(n)</sup>)f(x) and f(x).</li><br />
</ol><br />
Defined in [[zooref#ffk94|[FFK94]]].<br />
<br />
Contains [[Complexity Zoo:B#bqp|BQP]] [[zooref#fr98|[FR98]]], [[Complexity Zoo:W#wapp|WAPP]] [[zooref#bgm02|[BGM02]]], [[Complexity Zoo:L#lwpp|LWPP]], and [[Complexity Zoo:W#wpp|WPP]].<br />
<br />
Contained in [[#app|APP]] [[zooref#fen02|[Fen02]]].<br />
<br />
----<br />
<br />
===== <span id="awsat" style="color:red">AW[SAT]</span>: Alternating [[Complexity Zoo:W#wsat|W[SAT]]] =====<br />
Basically has the same relation to [[Complexity Zoo:W#wsat|W[SAT]]] as [[Complexity Zoo:P#pspace|PSPACE]] does to [[Complexity Zoo:N#np|NP]].<br />
<br />
The class of decision problems of the form (x,r,k<sub>1</sub>,...,k<sub>r</sub>) (r,k<sub>1</sub>,...,k<sub>r</sub> parameters), that are fixed-parameter reducible to the following problem, for some constant h:<br />
<ul><br />
'''Parameterized QBFSAT:''' Given a Boolean formula F (with no restriction on depth), over disjoint variable sets S<sub>1</sub>,...,S<sub>r</sub>. Does there exist an assignment to S<sub>1</sub> of Hamming weight k<sub>1</sub>, such that for all assignments to S<sub>2</sub> of Hamming weight k<sub>2</sub>, etc. (alternating 'there exists' and 'for all'), F is satisfied?<br />
</ul><br />
See [[Complexity Zoo:W#w1|W[1]]] for the definition of fixed-parameter reducibility.<br />
<br />
Defined in [[zooref#df99|[DF99]]].<br />
<br />
Contains [[#awstar|AW[*]]], and is contained in [[#awp|AW[P]]].<br />
<br />
----<br />
===== <span id="awstar" style="color:red">AW[*]</span>: Alternating [[Complexity Zoo:W#wstar|W[*]]] =====<br />
The union of [[#awt|AW[t]]] over all t.<br />
<br />
----<br />
===== <span id="awt" style="color:red">AW[t]</span>: Alternating [[Complexity Zoo:W#wt|W[t]]] =====<br />
Has the same relation to [[Complexity Zoo:W#wt|W[t]]] as [[Complexity Zoo:P#pspace|PSPACE]] does to [[Complexity Zoo:N#np|NP]].<br />
<br />
Same as [[#awsat|AW[SAT]]], except that the formula F can have depth at most t.<br />
<br />
Defined in [[zooref#df99|[DF99]]].<br />
<br />
Contained in [[#awstar|AW[*]]].<br />
<br />
[[zooref#dft98|[DFT98]]] show that for all t, [[#awt|AW[t]]] = [[#awstar|AW[*]]].<br />
<br />
----<br />
<br />
===== <span id="axp" style="color:red">AxP</span>: Approximable in Polynomial Time =====<br />
Usually called AP in the literature. I've renamed it AxP to distinguish it from the "other" [[#ap|AP]].<br />
<br />
The class of real-valued functions from {0,1}<sup>n</sup> to [0,1] that can be approximated within any &epsilon;>0 by a deterministic Turing machine in time polynomial in n and 1/&epsilon;.<br />
<br />
Defined by [[zooref#krc00|[KRC00]]], who also showed that the set of AxP machines is in [[Complexity Zoo:R#re|RE]].<br />
<br />
----<br />
===== <span id="axpp" style="color:red">AxPP</span>: Approximable in Probabilistic Polynomial Time =====<br />
Usually called APP. I've renamed it AxPP to distinguish it from the "other" [[#app|APP]].<br />
<br />
The class of real-valued functions from {0,1}<sup>n</sup> to [0,1] that can be approximated within any &epsilon;>0 by a probabilistic Turing machine in time polynomial in n and 1/&epsilon;.<br />
<br />
Defined by [[zooref#krc00|[KRC00]]], who also show the following:<br />
<ul><br />
<li>Approximating the acceptance probability of a Boolean circuit is AxPP-complete. The authors argue that this makes AxPP a more natural class than [[Complexity Zoo:B#bpp|BPP]], since the latter is not believed to have complete problems.</li><br />
<li>If AxPP = [[#axp|AxP]], then [[Complexity Zoo:B#bpp|BPP]] = [[Complexity Zoo:P#p|P]].</li><br />
<li>On the other hand, there exists an oracle relative to which [[Complexity Zoo:B#bpp|BPP]] = [[Complexity Zoo:P#p|P]] but AxPP does not equal [[#axp|AxP]].</li><br />
</ul><br />
AxPP is recursively enumerable [[zooref#jer07|[Jeř07]]].</div>Atnhttps://complexityzoo.net/index.php?title=Template:CZ-M&diff=6661Template:CZ-M2020-04-11T23:13:33Z<p>Atn: Fix misspelled class in TOC</p>
<hr />
<div>[[{{{1|}}}#ma|MA]] -<br />
[[{{{1|}}}#macc|MA<sup>cc</sup>]] -<br />
[[{{{1|}}}#maprime|MA']] -<br />
[[{{{1|}}}#mac0|MAC<sup>0</sup>]] -<br />
[[{{{1|}}}#mae|MA<sub>E</sub>]] -<br />
[[{{{1|}}}#maexp|MA<sub>EXP</sub>]] -<br />
[[{{{1|}}}#mal|mAL]] -<br />
[[{{{1|}}}#mapolylog|MA<sub>POLYLOG</sub>]] -<br />
[[{{{1|}}}#maxnp|MaxNP]] -<br />
[[{{{1|}}}#maxpb|MaxPB]] -<br />
[[{{{1|}}}#maxsnp|MaxSNP]] -<br />
[[{{{1|}}}#maxsnp0|MaxSNP<sub>0</sub>]] -<br />
[[{{{1|}}}#mconl|mcoNL]] -<br />
[[{{{1|}}}#minpb|MinPB]] -<br />
[[{{{1|}}}#mip|MIP]] -<br />
[[{{{1|}}}#mipstar|MIP*]] -<br />
[[{{{1|}}}#mipns|MIP<sup>ns</sup>]] -<br />
[[{{{1|}}}#mipexp|MIP<sub>EXP</sub>]] -<br />
[[{{{1|}}}#mkp|(M<sub>k</sub>)P]] -<br />
[[{{{1|}}}#ml|mL]] -<br />
[[{{{1|}}}#mm|MM]] -<br />
[[{{{1|}}}#mmsnp|MMSNP]] -<br />
[[{{{1|}}}#mnc1|mNC<sup>1</sup>]] -<br />
[[{{{1|}}}#mnl|mNL]] -<br />
[[{{{1|}}}#mnp|mNP]] -<br />
[[{{{1|}}}#modkl|Mod<sub>k</sub>L]] -<br />
[[{{{1|}}}#modl|ModL]] -<br />
[[{{{1|}}}#modkp|Mod<sub>k</sub>P]] -<br />
[[{{{1|}}}#modp|ModP]] -<br />
[[{{{1|}}}#modzkl|ModZ<sub>k</sub>L]] -<br />
[[{{{1|}}}#mp|mP]] -<br />
[[{{{1|}}}#mp2|MP]] -<br />
[[{{{1|}}}#mpc|MPC]] -<br />
[[{{{1|}}}#mppoly|mP/poly]] -<br />
[[{{{1|}}}#mtc0|mTC<sup>0</sup>]]</div>Atnhttps://complexityzoo.net/index.php?title=Complexity_Zoo:P&diff=6660Complexity Zoo:P2020-04-11T23:04:15Z<p>Atn: /* PSPACE: Polynomial-Space */</p>
<hr />
<div>__NOTOC__<br />
{{CZ-Letter-Menu|P}}<br />
<br />
<br />
===== <span id="p" style="color:red">P</span>: Polynomial-Time =====<br />
The class that started it all.<br />
<br />
The class of decision problems solvable in polynomial time by a Turing machine. (See also [[Complexity Zoo:F#fp|FP]], for function problems.)<br />
<br />
Defined in [[zooref#edm65|[Edm65]]], [[zooref#cob64|[Cob64]]], [[zooref#rab60|[Rab60]]], and other seminal early papers.<br />
<br />
Contains some highly nontrivial problems, including linear programming [[zooref#kha79|[Kha79]]] and finding a maximum matching in a general graph [[zooref#edm65|[Edm65]]].<br />
<br />
Contains the problem of testing whether an integer is prime [[zooref#aks02|[AKS02]]], an important result that improved on a proof requiring an assumption of the generalized Riemann hypothesis [[zooref#mil76|[Mil76]]].<br />
<br />
A decision problem is P-complete if it is in P, and if every problem in P can be reduced to it in [[Complexity Zoo:L#l|L]] (logarithmic space). The canonical P-complete problem is <i>circuit evaluation</i>: given a Boolean circuit and an input, decide what the circuit outputs when given the input.<br />
<br />
Important subclasses of P include [[Complexity Zoo:L#l|L]], [[Complexity Zoo:N#nl|NL]], [[Complexity Zoo:N#nc|NC]], and [[Complexity Zoo:S#sc|SC]].<br />
<br />
P is contained in [[Complexity Zoo:N#np|NP]], but whether they're equal seemed to be an open problem when I last checked.<br />
<br />
Efforts to generalize P resulted in [[Complexity Zoo:B#bpp|BPP]] and [[Complexity Zoo:B#bqp|BQP]].<br />
<br />
The nonuniform version is [[#ppoly|P/poly]], the monotone version is [[Complexity Zoo:M#mp|mP]], and versions over the real and complex number fields are [[#pr2|P<sub>R</sub>]] and [[#pc|P<sub>C</sub>]] respectively.<br />
<br />
In descriptive complexity, P can be defined by three different kind of formulae, [[#Complexity_Zoo:F#folfp|FO(lfp)]] which is also [[#Complexity_Zoo:F#fot|FO(<math>n^{O(1)}</math>)]]], and also as [[#Complexity_Zoo:S#sohorn|SO(Horn)]]<br />
<br />
P queries are exactly the one that can be written in the [[#Complexity_Zoo:S#while|While<sup>/cons</sup>]] languages.<br />
<br />
P is the class of decision problems solvable by a (logspace) ''uniform'' family of polynomial-size Boolean circuits.<br />
----<br />
<br />
===== <span id="plog" style="color:red">P/log</span>: [[#p|P]] With Logarithmic Advice =====<br />
Same as [[#ppoly|P/poly]], except that the advice string for input size n can have length at most logarithmic in n, rather than polynomial.<br />
<br />
Strictly contained in [[Complexity Zoo:I#iclogpoly|IC[log,poly]]].<br />
<br />
If [[Complexity Zoo:N#np|NP]] is contained in P/log then [[#p|P]] = [[Complexity Zoo:N#np|NP]].<br />
<br />
----<br />
===== <span id="ppoly" style="color:red">P/poly</span>: Nonuniform Polynomial-Time =====<br />
The class of decision problems solvable by a family of polynomial-size Boolean circuits. The family can be <i>nonuniform</i>; that is, there could be a completely different circuit for each input length.<br />
<br />
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.<br />
<br />
Contains [[Complexity Zoo:B#bpp|BPP]] by the progenitor of derandomization arguments [[zooref#adl78|[Adl78]]] [[zooref#kl82|[KL82]]]. By extension, BPP/poly, BPP/mpoly, and BPP/rpoly all equal P/poly. (By contrast, there is an oracle relative to which [[Complexity Zoo:B#bpplog|BPP/log]] does not equal [[Complexity Zoo:B#bppmlog|BPP/mlog]], while [[Complexity Zoo:B#bppmlog|BPP/mlog]] and [[Complexity Zoo:B#bpprlog|BPP/rlog]] are not equal relative to any oracle.)<br />
<br />
[[zooref#kl82|[KL82]]] showed that, if P/poly contains [[Complexity Zoo:N#np|NP]], then [[#ph|PH]] collapses to the second level, [[Complexity Zoo:S#sigma2p|&#931;<sub>2</sub>P]].<br />
<br />
They also showed:<br />
<ul><br />
<li>If [[#pspace|PSPACE]] is in P/poly then [[#pspace|PSPACE]] equals [[Complexity Zoo:S#sigma2p|&#931;<sub>2</sub>P]] &#8745; [[#pi2p|&#928;<sub>2</sub>P]].</li><br />
<li>If [[Complexity Zoo:E#exp|EXP]] is in P/poly then [[Complexity Zoo:E#exp|EXP]] = [[Complexity Zoo:S#sigma2p|&#931;<sub>2</sub>P]].</li><br />
</ul><br />
It was later shown that, if [[Complexity Zoo:N#np|NP]] is contained in P/poly, then [[#ph|PH]] collapses to [[Complexity Zoo:Z#zpp|ZPP]]<sup>[[Complexity Zoo:N#np|NP]]</sup> [[zooref#kw98|[KW98]]] and indeed [[Complexity Zoo:S#s2p|S<sub>2</sub>P]] [[zooref#cai01|[Cai01]]]. This seems close to optimal, since there exists an oracle relative to which the collapse cannot be improved to [[Complexity Zoo:D#delta2p|&#916;<sub>2</sub>P]] [[zooref#wil85|[Wil85]]].<br />
<br />
If [[Complexity Zoo:N#np|NP]] is not contained in P/poly, then [[#p|P]] does not equal [[Complexity Zoo:N#np|NP]]. Much of the effort toward separating [[#p|P]] from [[Complexity Zoo:N#np|NP]] is based on this observation. However, a 'natural proof' as defined by [[zooref#rr97|[RR97]]] cannot be used to show [[Complexity Zoo:N#np|NP]] is outside P/poly, if there is any pseudorandom generator in P/poly that has hardness 2<sup>&#937;(n^&#949;)</sup> for some &#949;&gt;0.<br />
<br />
If [[Complexity Zoo:N#np|NP]] is contained in P/poly, then [[Complexity Zoo:M#ma|MA]] = [[Complexity Zoo:A#am|AM]] [[zooref#aks95|[AKS+95]]]<br />
<br />
The monotone version of P/poly is [[Complexity Zoo:M#mppoly|mP/poly]].<br />
<br />
P/poly has measure 0 in [[Complexity Zoo:E#e|E]] with [[Complexity Zoo:S#sigma2p|&#931;<sub>2</sub>P]] oracle [[zooref#may94b|[May94b]]].<br />
<br />
Strictly contains [[Complexity Zoo:I#iclogpoly|IC[log,poly]]] and [[#plog|P/log]].<br />
<br />
----<br />
<br />
===== <span id="psharpp" style="color:red">P<sup>#P</sup></span>: [[#p|P]] With [[Complexity Zoo:Symbols#sharpp|#P]] Oracle =====<br />
I decided this class is so important that it deserves an entry of its own, apart from [[Complexity Zoo:Symbols#sharpp|#P]].<br />
<br />
Contains [[#ph|PH]] [[zooref#tod89|[Tod89]]], and is contained in [[#pspace|PSPACE]].<br />
<br />
Equals [[#ppp2|P<sup>PP</sup>]] (exercise for the visitor).<br />
<br />
----<br />
===== <span id="psharpp1" style="color:red">P<sup>#P[1]</sup></span>: [[#p|P]] With Single Query To [[Complexity Zoo:Symbols#sharpp|#P]] Oracle =====<br />
Contains [[#ph|PH]] [[zooref#tod89|[Tod89]]].<br />
<br />
----<br />
===== <span id="pctc" style="color:red">P<sub>CTC</sub></span>: [[#p|P]] With Closed Time Curves =====<br />
Same as [[#p|P]] with access to bits along a closed time curve.<br />
<br />
Implicitly defined in [[zooref#aar05c|[Aar05c]]], where it was shown that PSPACE = P<sub>CTC</sub>.<br />
<br />
See also [[Complexity Zoo:B#bqpctc|BQP<sub>CTC</sub>]].<br />
<br />
----<br />
===== <span id="para" style="color:red">para-</span>: Parameterized Complexity =====<br />
The para- prefix indicates that a complexity class is parameterized by some other measure of complexity. Specifically, a language L is in the parameterized class para-C, if there is an alphabet A and a computable function pi(k) -> A*, such that every (Q,k) is in para-L if and only if (Q,pi(k)) in L.<br />
<br />
The prototypical example (as well the violation of the naming convention) is para-P, which is almost always known as [[Complexity Zoo:FPT#fpt|FPT]], which is equal to DTIME(f(k)n^c) for some constant c.<br />
<br />
Space-parameterized examples include [[#para-L|para-L]] and [[#para-NL|para-NL]], which are equal to DSPACE(f(k)+log(n)) and NDSPACE(f(k)+log(n)), respectively.<br />
<br />
Compare with the slicewise complexity classes [[Complexity Zoo:X#x|X-]], such as [[Complexity Zoo:X#x|X-]].<br />
<br />
Discussed in:<br />
J. Flum and M. Grohe. Describing parameterized complexity classes. Information and Computation.<br />
and<br />
Elberfeld M., Stockhusen C., Tantau T. (2012) On the Space Complexity of Parameterized Problems.<br />
<br />
----<br />
===== <span id="paral" style="color:red">para-L</span>: Parameterized Logspace =====<br />
[[#para|para-]] version of [[Complexity Zoo:L#l|L]]. Equivalent to DSPACE(f(k)+log(n)) for some computable function f. Compare with slicewise parameterized logspace, [[Complexity Zoo:X#xl|XL]].<br />
<br />
Parameterized vertex cover (is there a vertex cover of size at most k) is complete for para-L. (Elberfeld et al, 2012)<br />
<br />
----<br />
===== <span id="paranl" style="color:red">para-NL</span>: Parameterized Nondeterministic Logspace =====<br />
[[#para|para-]] version of [[Complexity Zoo:N#nl|NL]]. Equivalent to NDSPACE(f(k)+log(n)) for some computable function f. Compare with slicewise parameterized nondeterministic logspace, [[Complexity Zoo:X#xnl|XNL]].<br />
<br />
It seems open whether there are natural complete problems for para-NL. However, the related class [[#paranlflog|para-NL[f log]]] has many natural complete problems.<br />
<br />
----<br />
===== <span id="paranlflog" style="color:red">para-NL[f log]</span>: Parameterized Nondeterministic Logspace =====<br />
Like [[#paranl|para-NL]], but where the number of nondeterministic branches is bounded by O(f(k) log(n)).<br />
<br />
A natural complete is problem parameterized distance: is there a path on directed graph G from vertex s to v, of length at most k? (Elberfeld et al, 2012)<br />
<br />
para-NL[f log] is contained within [[Complexity Zoo:X#xl|XL]], slicewise logspace.<br />
<br />
----<br />
===== <span id="parap" style="color:red">para-P</span>: Parameterized Polynomial time. =====<br />
para-P is a less common name for [[Complexity Zoo:F#fpt|FPT]], but in line with other [[#para|para-]] classes naming conventions. Its slicewise counterpart is still called [[Complexity Zoo:X#xp|XP]].<br />
----<br />
<br />
===== <span id="pac0" style="color:red">PAC<sup>0</sup></span>: Probabilistic [[Complexity Zoo:A#ac0|AC<sup>0</sup>]] =====<br />
The Political Action Committee for computational complexity research.<br />
<br />
The class of problems for which there exists a [[Complexity Zoo:D#diffac0|DiffAC<sup>0</sup>]] function f such that the answer is "yes" on input x if and only if f(x)>0.<br />
<br />
Equals [[Complexity Zoo:T#tc0|TC<sup>0</sup>]] and [[Complexity Zoo:C#cequalsac0|C<sub>=</sub>AC<sup>0</sup>]] under logspace uniformity [[zooref#abl98|[ABL98]]].<br />
<br />
----<br />
===== <span id="pbp" style="color:red">PBP</span>: Polynomial-Size Branching Program =====<br />
Same as [[#kpbp|k-PBP]] but with no width restriction.<br />
<br />
Equals [[Complexity Zoo:L#l/poly|L/poly]] [[zooref#cob66|[Cob66]]].<br />
<br />
Contains [[#pobdd|P-OBDD]], [[Complexity Zoo:B#bpdp|BP<sub>d</sub>(P)]].<br />
<br />
----<br />
<br />
===== <span id="kpbp" style="color:red">k-PBP</span>: Polynomial-Size Width-k Branching Program =====<br />
A <i>branching program</i> 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.<br />
<br />
The <i>size</i> of the branching program is the number of vertices. The branching program has <i>width k</i> 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.<br />
<br />
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.)<br />
<br />
k-PBP equals (nonuniform) [[Complexity Zoo:N#nc1|NC<sup>1</sup>]] for constant k at least 5 [[zooref#bar89|[Bar89]]]. On the other hand, 4-PBP is in [[Complexity Zoo:A#acc0|ACC<sup>0</sup>]] [[zooref#bt88|[BT88]]].<br />
<br />
Contained in k-[[Complexity Zoo:E#eqbp|EQBP]], as well as [[#pbp|PBP]].<br />
<br />
See also [[Complexity Zoo:B#bpdp|BP<sub>d</sub>(P)]].<br />
----<br />
<br />
===== <span id="pc" style="color:red">P<sub>C</sub></span>: Polynomial-Time Over The Complex Numbers =====<br />
An analog of [[#p|P]] for Turing machines over a complex number field.<br />
<br />
Defined in [[zooref#bcs97|[BCS+97]]].<br />
<br />
See also [[#pr2|P<sub>R</sub>]], [[Complexity Zoo:N#npc2|NP<sub>C</sub>]], [[Complexity Zoo:N#npr|NP<sub>R</sub>]], [[Complexity Zoo:V#vp|VP<sub>k</sub>]].<br />
<br />
----<br />
===== <span id="pcc" style="color:red">P<sup>cc</sup></span>: Communication Complexity [[#p|P]] =====<br />
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<sup>cc</sup> 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.<br />
<br />
Note that all functions of the form above are solvable given <math>O(n)</math> bits of communication, since no bounds are placed on the computational abilities of Alice and Bob. Thus, when discussing this class, "polynomially" is sometimes used in place of "polylogarithmically."<br />
<br />
Is strictly contained in [[Complexity Zoo:N#npcc|NP<sup>cc</sup>]] and in [[Complexity Zoo:B#bppcc|BPP<sup>cc</sup>]] because of the [[Complexity Garden#equality|EQUALITY]] problem.<br />
<br />
If the classes are defined in terms of total functions, then P<sup>cc</sup> = [[Complexity Zoo:N#npcc|NP<sup>cc</sup>]] &#8745; [[Complexity Zoo:N#npcc|coNP<sup>cc</sup>]] = [[Complexity Zoo:U#upcc|UP<sup>cc</sup>]].<br />
<br />
Defined in [[zooref#bfs86|[BFS86]]].<br />
<br />
----<br />
<br />
===== <span id="pkcc" style="color:red">P<sub><math>k</math></sub><sup>cc</sup></span>: [[#pcc|P<sup>cc</sup>]] in NOF model, <math>k</math> players =====<br />
<br />
Like [[#pcc|P<sup>cc</sup>]], but with <math>k</math> players, where each player can see all of the other player's bits, but not their own. Intuitively, each player has their bits written on their forehead.<br />
<br />
More formally, P<sub><math>k</math></sub><sup>cc</sup> is the class of functions <math>F:X_1\times X_2 \times \cdots \times X_k \to \{0,1\}</math> where for all <math>i\in[1..k]</math>, <math>X_k\in\{0,1\}^n</math>, such that <math>F</math> is solvable in a deterministic sense by <math>k</math> players, each of which is aware of all inputs <math>X_i</math> other than his own, and such that <math>O\left(\mathrm{poly}(\log n)\right)</math> bits of communication are used.<br />
<br />
P<sub><math>k</math></sub><sup>cc</sup> is trivially contained in {{zcls|b|bppkcc|BPP<sub><math>k</math></sub><sup>cc</sup>}}, {{zcls|r|rpkcc|RP<sub><math>k</math></sub><sup>cc</sup>}} and {{zcls|n|npkcc|NP<sub><math>k</math></sub><sup>cc</sup>}}.<br />
<br />
----<br />
<br />
===== <span id="pcd" style="color:red">PCD(r(n),q(n))</span>: Probabilistically Checkable Debate =====<br />
The class of decision problems decidable by a <i>probabilistically checkable debate system</i>, as follows.<br />
<br />
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)) <i>nonadaptive</i> 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.<br />
<br />
Defined in [[zooref#cfl93|[CFL+93]]], who also showed that PCD(log n, 1) = [[#pspace|PSPACE]]. This result was used to show that certain problems are [[#pspace|PSPACE]]-hard even to approximate.<br />
<br />
Contained in [[Complexity Zoo:G#gpcd|GPCD]](r(n),q(n)).<br />
<br />
----<br />
===== <span id="pclose" style="color:red">P-Close</span>: Problems Close to [[#p|P]] =====<br />
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.<br />
<br />
Defined in [[zooref#yes83|[Yes83]]].<br />
<br />
Contains [[Complexity Zoo:A#almostp|Almost-P]] and is contained in [[#ppoly|P/poly]] [[zooref#sch86|[Sch86]]].<br />
<br />
----<br />
<br />
===== <span id="pcp" style="color:red">PCP(r(n),q(n))</span>: Probabilistically Checkable Proof =====<br />
The class of decision problems such that a "yes" answer can be verified by a <i>probabilistically checkable proof</i>, as follows.<br />
<br />
The verifier is a polynomial-time Turing machine with access to O(r(n)) uniformly random bits. It has random access to a <i>proof</i> (which might be exponentially long), but can query only O(q(n)) bits of the proof.<br />
<br />
Then we require the following:<br />
<ol><br />
<li>If the answer is "yes," there exists a proof such that the verifier accepts with certainty.</li><br />
<li>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).</li><br />
</ol><br />
Defined in [[zooref#as98|[AS98]]].<br />
<br />
By definition [[Complexity Zoo:N#np|NP]] = PCP(0,poly(n)).<br />
<br />
[[Complexity Zoo:M#mip|MIP]] = PCP(poly(n),poly(n)).<br />
<br />
PCP(r(n),q(n)) is contained in [[Complexity Zoo:N#ntime|NTIME]](2<sup>O(r(n))</sup>q(n) + poly(n)).<br />
<br />
[[Complexity Zoo:N#np|NP]] = PCP(log n, log n) [[zooref#as98|[AS98]]].<br />
<br />
In fact, [[Complexity Zoo:N#np|NP]] = PCP(log n, 1) [[zooref#alm98|[ALM+98]]]!<br />
<br />
On the other hand, if [[Complexity Zoo:N#np|NP]] is contained in PCP(o(log n), o(log n)), then [[#p|P]] = [[Complexity Zoo:N#np|NP]] [[zooref#fgl91|[FGL+91]]].<br />
<br />
Also, even though there exists an oracle relative to which [[Complexity Zoo:N#np|NP]] = [[Complexity Zoo:E#exp|EXP]] [[zooref#hel84|[Hel84]]], if we could show there exists an oracle relative to which PCP(log n, 1) = [[Complexity Zoo:E#exp|EXP]], then we'd have proved [[#p|P]] not equal to [[Complexity Zoo:N#np|NP]] [[zooref#for94|[For94]]].<br />
<br />
Another weird oracle fact: since [[Complexity Zoo:N#np|NP]] does not equal [[Complexity Zoo:N#nexp|NEXP]] [[zooref#sfm78|[SFM78]]], PCP(log n, log n) does not equal PCP(poly(n), poly(n)). However, there exist oracles relative to which the latter inequality is false [[zooref#hcc92|[HCC+92]]].<br />
<br />
----<br />
===== <span id="pdqp" style="color:red">PDQP</span>: Product Dynamical Quantum Polynomial time =====<br />
<br />
This class is a generalization of [[Complexity Zoo:B#bqp|BQP]] where one is allowed to perform measuresments without collapsing the wavefunction.[[zooref#abfl14|[ABFL14]]]<br />
<br />
Unlike, BQP this is likely to be a not physically realizable class.<br />
<br />
Contains [[Complexity Zoo:S#szk|SZK]] and thus contains graph isomorphism.<br />
<br />
There is an oracle relative to which BQP is not equal to PDQP and an oracle relative to which NP is not contained in PDQP. <br />
<br />
PDQP can perform unordered searches faster than BQP. <br />
<br />
Compare [[Complexity Zoo:D#DQP|DQP]]. <br />
----<br />
<br />
===== <span id="permup" style="color:red">PermUP</span>: Self-Permuting [[Complexity Zoo:U#up|UP]] =====<br />
The class of languages L in [[Complexity Zoo:U#up|UP]] such that the mapping from an input x to the unique witness for x is a permutation of L.<br />
<br />
Contains [[#p|P]].<br />
<br />
Defined in [[zooref#ht03|[HT03]]], where it was also shown that the closure of PermUP under polynomial-time one-to-one reductions is [[Complexity Zoo:U#up|UP]].<br />
<br />
On the other hand, they show that if PermUP = [[Complexity Zoo:U#up|UP]] then [[Complexity Zoo:E#e|E]] = [[Complexity Zoo:U#ue|UE]].<br />
<br />
See also: [[Complexity Zoo:S#selfnp|SelfNP]].<br />
<br />
----<br />
===== <span id="pexp" style="color:red">PEXP</span>: Probabilistic Exponential-Time =====<br />
Has the same relation to [[Complexity Zoo:E#exp|EXP]] as [[#pp|PP]] does to [[#p|P]].<br />
<br />
Is not contained in [[#ppoly|P/poly]] [[zooref#bft98|[BFT98]]].<br />
<br />
----<br />
===== <span id="pf" style="color:red">PF</span>: Alternate Name for [[Complexity Zoo:F#fp|FP]] =====<br />
<br />
----<br />
===== <span id="pfchk" style="color:red">PFCHK(t(n))</span>: Proof-Checker =====<br />
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 <i>proof string</i> of unbounded length.<br />
<ul><br />
<li>If the answer is "yes," then there exists a value of the proof string such that all computation paths accept.</li><br />
<li>If the answer is "no," then for all values of the proof string, there exists a computation path that rejects.</li><br />
</ul><br />
Credited in [[zooref#for94|[For94]]] to S. Arora, R. Impagliazzo, and U. Vazirani.<br />
<br />
An interesting question is whether [[Complexity Zoo:N#np|NP]] = PFCHK(log n) relative to all possible oracles. Fortnow [[zooref#for94|[For94]]] observes that the answer depends on what oracle access mechanism is used.<br />
<br />
----<br />
===== <span id="ph" style="color:red">PH</span>: Polynomial-Time Hierarchy =====<br />
Let &#916;<sub>0</sub>P = &#931;<sub>0</sub>P = &#928;<sub>0</sub>P = [[#p|P]]. Then for i&gt;0, let<br />
<ul><br />
<li>&#916;<sub>i</sub>P = [[#p|P]] with &#931;<sub>i-1</sub>P oracle.</li><br />
<li>&#931;<sub>i</sub>P = [[Complexity Zoo:N#np|NP]] with &#931;<sub>i-1</sub>P oracle.</li><br />
<li>&#928;<sub>i</sub>P = [[Complexity Zoo:C#conp|coNP]] with &#931;<sub>i-1</sub>P oracle.</li><br />
</ul><br />
Then PH is the union of these classes for all nonnegative constant i.<br />
<br />
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 &phi;(x,y,z,w,...)," where y,z,w,... are polynomial-size strings and &phi; 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 [[Complexity Zoo:N#np|NP]] oracle queries and the second one doesn't, but it is.<br />
<br />
Defined in [[zooref#sto76|[Sto76]]].<br />
<br />
Contained in [[#p|P]] with a [[#pp|PP]] oracle [[zooref#tod89|[Tod89]]].<br />
<br />
Contains [[Complexity Zoo:B#bpp|BPP]] [[zooref#lau83|[Lau83]]].<br />
<br />
Relative to a random oracle, PH is strictly contained in [[#pspace|PSPACE]] with probability 1 [[zooref#cai86|[Cai86]]].<br />
<br />
Furthermore, there exist oracles separating any &#931;<sub>i</sub>P from &#931;<sub>i+1</sub>P. In fact, relative to a random oracle, the hierarchy is infinite: each level is strictly contained in the next, with probability 1 [[zooref#rst15|[RST15]]] (this was an open problem for 29 years). Previously, it had been known that if it had collapsed relative to a random oracle, then it would have collapsed unrelativized [[zooref#boo94|[Boo94]]].<br />
<br />
It was shown in [[zooref#cp07|[CPO7]]] that if the NP Machine Hypothesis holds, then<br />
<math><br />
\mathsf{P}^{\mathrm{SAT}[1]} = \mathsf{P}^{\mathrm{SAT}[2]} \Rightarrow \mathsf{PH} \subseteq \mathsf{NP}<br />
</math>.<br />
<br />
For a compendium of problems complete for different classes of the Polynomial Hierarchy see [[zooref#sch02a|[Sch02a]]] and [[zooref#sch02b|[Sch02b]]].<br />
<br />
PH is equal to the set of boolean queries recognizable by a concurent random acess machine using exponentially many processors and constant time[[zooref#imm89|[Imm89]]].<br />
<br />
Since NP is the class of query expressible in second-order existantial logic, PH can also be defined as the query expressible in [[#Complexity_Zoo:S#so|second-order logic]].<br />
----<br />
<br />
===== <span id="phcc" style="color:red">PH<sup>cc</sup></span>: Communication Complexity [[#ph|PH]] =====<br />
The polynomial hierarchy for communication complexity, naturally built with [[Complexity Zoo:N#npcc|NP<sup>cc</sup>]] and [[Complexity Zoo:C#conpcc|coNP<sup>cc</sup>]] forming the first level. Specifically, a cost-k protocol in the PH<sup>cc</sup> model corresponds to a constant-depth 2<sup>k</sup>-ary tree whose internal nodes are alternating layers of AND and OR gates, and whose leaves represent (the indicator functions of) either rectangles or complements of rectangles, as appropriate.<br />
<br />
It is unknown whether &#931;<sub>2</sub><sup>cc</sup> equals &#928;<sub>2</sub><sup>cc</sup>.<br />
<br />
Defined in [[zooref#bfs86|[BFS86]]], where it was also shown (among other things) that [[Complexity Zoo:B#bppcc|BPP<sup>cc</sup>]] is contained in &#931;<sub>2</sub><sup>cc</sup> &#8745; &#928;<sub>2</sub><sup>cc</sup>.<br />
<br />
----<br />
<br />
===== <span id="phi2p" style="color:red">&#934;<sub>2</sub>P</span>: Second Level of the Symmetric Hierarchy, Alternative Definition =====<br />
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<br />
<ol><br />
<li>For all y, there exists a z for which P(x,y,z).</li><br />
<li>For all z, there exists a y for which P(x,y,z).</li><br />
</ol><br />
Contained in [[Complexity Zoo:S#sigma2p|&#931;<sub>2</sub>P]] and [[#pi2p|&#928;<sub>2</sub>P]].<br />
<br />
Defined in [[zooref#can96|[Can96]]], where it was also observed that &#934;<sub>2</sub>P = [[Complexity Zoo:S#s2p|S<sub>2</sub>P]].<br />
<br />
----<br />
===== <span id="php" style="color:red">PhP</span>: Physical Polynomial-Time =====<br />
Defined by Valiant [[zooref#val03|[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|P]] and [[Complexity Zoo:B#bpp|BPP]], but that it is open whether PhP contains [[Complexity Zoo:B#bqp|BQP]], since no scalable quantum computing proposal has been demonstrated beyond reasonable doubt.<br />
<br />
For what it's worth, the present zookeeper has more qualms about admitting [[Complexity Zoo:D#dtime|DTIME]](n<sup>1000</sup>) into PhP than [[Complexity Zoo:B#bqtime|BQTIME]](n<sup>2</sup>). 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<sup>k</sup> with k in the low hundreds.) In practice, less than 10<sup>50</sup> bits and less than 10<sup>80</sup> 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.)<br />
<br />
The present veterinarian concurs that PhP is an unhealthy animal, although it is valid to ask whether [[Complexity Zoo:B#bqp|BQP]] is a realistic class.<br />
<br />
----<br />
<br />
===== <span id="pi2p" style="color:red">&#928;<sub>2</sub>P</span>: [[Complexity Zoo:C#conp|coNP]] With [[Complexity Zoo:N#np|NP]] Oracle =====<br />
Complement of [[Complexity Zoo:S#sigma2p|&#931;<sub>2</sub>P]].<br />
<br />
Along with [[Complexity Zoo:S#sigma2p|&#931;<sub>2</sub>P]], comprises the second level of [[#ph|PH]], the polynomial hierarchy. For any fixed k, there is a problem in &#928;<sub>2</sub>P &#8745; [[Complexity Zoo:S#sigma2p|&#931;<sub>2</sub>P]] that cannot be solved by circuits of size n<sup>k</sup> [[zooref#kan82|[Kan82]]].<br />
<br />
----<br />
===== <span id="pinc" style="color:red">PINC</span>: Polynomial Ignorance of Names of Classes =====<br />
(Actually, I've since been informed that PINC means "Incremental Polynomial-Time.")<br />
<br />
The class of function problems, f:{0,1}<sup>n</sup>-&gt;{0,1}<sup>m</sup>, such that the k<sup>th</sup> output bit is computable in time polynomial in n and k.<br />
<br />
Defined in [[zooref#jy88|[JY88]]].<br />
<br />
Contained in [[#pio|PIO]]. This containment is strict, since if m=2<sup>n</sup> (say), then computing the first bit of f(x) might be [[Complexity Zoo:E#exp|EXP]]-complete.<br />
<br />
----<br />
===== <span id="pio" style="color:red">PIO</span>: Polynomial Input Output =====<br />
The class of function problems, f:{0,1}<sup>n</sup>-&gt;{0,1}<sup>m</sup>, 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.<br />
<br />
Defined in [[zooref#yan81|[Yan81]]].<br />
<br />
Strictly contains [[#pinc|PINC]].<br />
<br />
----<br />
===== <span id="pk" style="color:red">P<sup>K</sup></span>: [[#p|P]] With Kolmogorov-Complexity Oracle =====<br />
[[#p|P]] equipped with an oracle that, given a string x, returns the length of the shortest program that outputs x.<br />
<br />
A similar class was defined in [[zooref#abk02|[ABK+02]]], where it was also shown that P<sup>K</sup> contains [[#pspace|PSPACE]]. It is not known whether P<sup>K</sup> contains all of [[Complexity Zoo:R#r|R]], or even any recursive problem not in [[#pspace|PSPACE]].<br />
<br />
See also: [[Complexity Zoo:B#bppkt|BPP<sup>KT</sup>]].<br />
<br />
----<br />
===== <span id="pkc" style="color:red">PKC</span>: Perfect Knowledge Complexity =====<br />
Has the same relation to [[#pzk|PZK]] as [[#skc|SKC]] does to [[Complexity Zoo:S#szk|SZK]].<br />
<br />
Defined in [[zooref#gp91|[GP91]]].<br />
<br />
----<br />
===== <span id="pl" style="color:red">PL</span>: Probabilistic [[Complexity Zoo:L#l|L]] =====<br />
Has the same relation to [[Complexity Zoo:L#l|L]] that [[#pp|PP]] has to [[#p|P]].<br />
<br />
Contains [[Complexity Zoo:B#bpl|BPL]].<br />
<br />
PL<sup>PL</sup> = PL (see [[zooref#ho02|[HO02]]]).<br />
<br />
----<br />
===== <span id="pl1" style="color:red">PL<sub>1</sub></span>: Polynomially-Bounded L<sub>1</sub> Spectral Norm =====<br />
The class of Boolean functions f:{-1,1}<sup>n</sup>->{-1,1} such that the sum of absolute values of Fourier coefficients of f is bounded by a polynomial in n.<br />
<br />
Defined in [[zooref#bs90|[BS90]]], where it was also shown that PL<sub>1</sub> is contained in [[#pt1|PT<sub>1</sub>]] (and this inclusion is strict).<br />
<br />
----<br />
===== <span id="plinfinity" style="color:red">PL<sub>&#8734;</sub></span>: Polynomially-Bounded L<sub>&#8734;</sub><sup>-1</sup> Spectral Norm =====<br />
The class of Boolean functions f:{-1,1}<sup>n</sup>->{-1,1} such that the maximum of |&alpha;|<sup>-1</sup>, over all Fourier coefficients &alpha; of f, is upper-bounded by a polynomial in n.<br />
<br />
Defined in [[zooref#bs90|[BS90]]], where it was also shown that PL<sub>&#8734;</sub> contains [[#pt1|PT<sub>1</sub>]] (and this inclusion is strict).<br />
<br />
----<br />
<br />
===== <span id="plf" style="color:red">PLF</span>: Polynomial Leaf =====<br />
Defined in [[zooref#pap90|[Pap90]]].<br />
<br />
I believe it's the same as [[#ppa|PPA]].<br />
<br />
----<br />
===== <span id="pll" style="color:red">PLL</span>: Polynomial Local Lemma =====<br />
The class of [[Complexity Zoo:T#tfnp|TFNP]] function problems that are guaranteed to have a solution because of the Lov&aacute;sz Local Lemma. Defined in [[zooref#pap94b|[Pap94b]]].<br />
<br />
----<br />
===== <span id="pls" style="color:red">PLS</span>: Polynomial Local Search =====<br />
The subclass of [[Complexity Zoo:T#tfnp|TFNP]] function problems that are guaranteed to have a solution because of the lemma that "every finite directed acyclic graph has a sink."<br />
<br />
More precisely, for each input, there's a finite set of <i>solutions</i> (i.e. strings), and a polynomial-time algorithm that computes a <i>cost</i> for each solution, and a <i>neighboring solution</i> 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.)<br />
<br />
(<i>Note:</i> In the Zookeeper's humble opinion, PLS <i>should</i> have been defined as follows: there exist polynomial-time algorithms that compute the cost of a solution, and the set of <i>all</i> 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.)<br />
<br />
(<i>Note to Note:</i> The equivalance of these classes was shown (though not stated explicitly) in Theorem 1 of [[zooref#jpy88|[JPY88]]].) <!-- by Domotor Palvolgyi--><br />
<br />
Defined in [[zooref#jpy88|[JPY88]]], [[zooref#py88|[PY88]]].<br />
<br />
There exists an oracle relative to which PLS is not contained in [[Complexity Zoo:F#fbqp|FBQP]] [[zooref#aar03|[Aar03]]].<br />
<br />
Also, there exist oracles relative to which PLS is not contained in [[#ppa|PPA]] [[zooref#bm04|[BM04]]], and [[#ppa|PPA]] and [[#ppp|PPP]] are not contained in PLS [[zooref#mor01|[Mor01]]].<br />
<br />
Whether PLS is not in [[#ppp|PPP]] relative to some oracle remains open.<br />
<br />
[[zooref#ct07|[CT07]]] conjecture that if [[#ppad|PPAD]] is in [[#p|P]], then [[#pls|PLS]] is in [[#p|P]].<br />
----<br />
<br />
===== <span id="pnp" style="color:red">P<sup>NP</sup></span>: [[#p|P]] With Oracle Access To [[Complexity Zoo:N#np|NP]] =====<br />
See [[Complexity Zoo:D#delta2p|&#916;<sub>2</sub>P]].<br />
<br />
----<br />
<br />
===== <span id="pnpcc" style="color:red">P<sup>NPcc</sup></span>: Communication Complexity [[#pnp|P<sup>NP</sup>]] =====<br />
<br />
Not contained in [[Complexity Zoo:P#ppcc|PP<sup>cc</sup>]] [[zooref#bvw07|[BVW07]]].<br />
<br />
Does not contain [[Complexity Zoo:B#bppcc|BPP<sup>cc</sup>]] if partial functions are allowed [[zooref#pps14|[PPS14]]].<br />
<br />
Contained in [[Complexity Zoo:U#upostbppcc|UPostBPP<sup>cc</sup>]].<br />
<br />
----<br />
<br />
===== <span id="pparnp" style="color:red">P<sup>||NP</sup></span>: [[#p|P]] With Parallel Queries To [[Complexity Zoo:N#np|NP]] =====<br />
Equals [[#pnplog|P<sup>NP[log]</sup>]] ([[zooref#bh91|[BH91]]] and [[zooref#hem89|[Hem89]]] independently).<br />
<br />
----<br />
===== <span id="pnpk" style="color:red">P<sup>NP[k]</sup></span>: [[#p|P]] With k [[Complexity Zoo:N#np|NP]] Queries(for constant k) =====<br />
Equals [[#p|P]] with 2<sup>k</sup>-1 parallel queries to [[Complexity Zoo:N#np|NP]] (i.e. queries that do not depend on the outcomes of previous queries) ([[zooref#bh91|[BH91]]] and [[zooref#hem89|[Hem89]]] independently).<br />
<br />
If P<sup>NP[1]</sup> = P<sup>NP[2]</sup>, then P<sup>NP[1]</sup> = [[#pnplog|P<sup>NP[log]</sup>]] and indeed [[#ph|PH]] collapses to &Delta;<sub>3</sub>P (attributed in [[zooref#har87b|[Har87b]]] to J. Kadin).<br />
<br />
----<br />
===== <span id="pnplog" style="color:red">P<sup>NP[log]</sup></span>: [[#p|P]] With Log [[Complexity Zoo:N#np|NP]] Queries =====<br />
Also known as [[Complexity Zoo:T#theta2p|Θ<sub>2</sub><sup>P</sup>]].<br />
<br />
The class of decision problems solvable by a [[#p|P]] machine, that can make O(log n) queries to an [[Complexity Zoo:N#np|NP]] oracle (where n is the length of the input).<br />
<br />
Equals [[#pparnp|P<sup>&#124;&#124;NP</sup>]], the class of decision problems solvable by a [[#p|P]] machine that can make polynomially many <i>nonadaptive</i> queries to an [[Complexity Zoo:N#np|NP]] oracle (i.e. queries that do not depend on the outcomes of previous queries) ([[zooref#bh91|[BH91]]] and [[zooref#hem89|[Hem89]]] independently).<br />
<br />
P<sup>NP[log]</sup> is contained in [[#pp|PP]] [[zooref#bhw89|[BHW89]]].<br />
<br />
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<sup>NP[log]</sup> [[zooref#hhr97|[HHR97]]].<br />
<br />
Contains [[#pnpk|P<sup>NP[k]</sup>]] for all constants k.<br />
<br />
----<br />
<br />
===== <span id="pnplog2" style="color:red">P<sup>NP[log^2]</sup></span>: [[#p|P]] With Log<sup>2</sup> [[Complexity Zoo:N#np|NP]] Queries =====<br />
Same as [[#pnplog|P<sup>NP[log]</sup>]], except that now log<sup>2</sup> queries can be made.<br />
<br />
The model-checking problem for a certain temporal logic is P<sup>NP[log^2]</sup>-complete [[zooref#sch03|[Sch03]]].<br />
<br />
For all k ≥ 1, [[#p|P]] with log<sup>k</sup> adaptive queries to [[Complexity Zoo:N#np|NP]] coincides with [[#p|P]] with log<sup>k−1</sup> rounds of (polynomially many) nonadaptive queries [[zooref#cs92|[CS92]]].<br />
<br />
----<br />
<br />
===== <span id="pobdd" style="color:red">P-OBDD</span>: Polynomial-Size Ordered Binary Decision Diagram =====<br />
An <i>ordered binary decision diagram (OBDD)</i> is a branching program (see [[#kpbp|k-PBP]]), with the additional constraint that if x<sub>i</sub> is queried before x<sub>j</sub> on any path, then i&lt;j.<br />
<br />
Then P-OBDD is the class of decision problems solvable by polynomial-size OBDD's.<br />
<br />
Contained in [[#pbp|PBP]], as well as [[Complexity Zoo:B#bppobdd|BPP-OBDD]].<br />
<br />
----<br />
===== <span id="podn" style="color:red">PODN</span>: Polynomial Odd Degree Node =====<br />
The subclass of [[Complexity Zoo:T#tfnp|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."<br />
<br />
Equals [[#ppa|PPA]] [[zooref#pap90|[Pap90]]].<br />
<br />
----<br />
===== <span id="polyl" style="color:red">polyL</span>: Polylogarithmic Space =====<br />
Equals [[Complexity Zoo:D#dspace|DSPACE]]((log n)<sup>c</sup>).<br />
<br />
In contrast to [[Complexity Zoo:L#l|L]], which is contained in [[#p|P]], it is not known if polyL is contained in [[#p|P]] or vice versa. On the other hand, we do know that polyL does not equal [[#p|P]], since (for example) polyL does not have complete problems under many-to-one logspace reductions.<br />
<br />
----<br />
===== <span id="postbpp" style="color:red">PostBPP</span>: [[Complexity Zoo:B#bpp|BPP]] With Postselection =====<br />
Alias for [[Complexity Zoo:B#bpppath|BPP<sub>path</sub>]].<br />
<br />
----<br />
===== <span id="postbppcc" style="color:red">PostBPP<sup>cc</sup></span>: Communication Complexity [[Complexity Zoo:P#postbpp|PostBPP]] =====<br />
<br />
The corresponding model consists of randomized protocols that may output 0, 1, or "abort", such that on every input, the non-abort probability is at least some &alpha;>0 (which is to be thought of as a function of n), and conditioned on not aborting, the output is correct with probability at least 2/3. The cost of a protocol is defined to be its communication cost plus log(1/&alpha;).<br />
<br />
Contained in, but does not equal, [[Complexity Zoo:P#ppcc|PP<sup>cc</sup>]] [[zooref#kla03|[Kla03]]].<br />
<br />
Contained in [[Complexity Zoo:P#phcc|PH<sup>cc</sup>]].<br />
<br />
The complexity measure corresponding to PostBPP<sup>cc</sup> is equivalent to the "extended discrepancy bound" [[zooref#gl14|[GL14]]].<br />
<br />
----<br />
<br />
===== <span id="postbqp" style="color:red">PostBQP</span>: [[Complexity Zoo:B#bqp|BQP]] With Postselection =====<br />
A class inspired by the proverb, "if at first you don't succeed, try, try again."<br />
<br />
Formally, the class of decision problems solvable by a [[Complexity Zoo:B#bqp|BQP]] machine such that<br />
<ul><br />
<li>If the answer is 'yes' then the second qubit has at least 2/3 probability of being measured 1, <i>conditioned</i> on the first qubit having been measured 1.</li><br />
<li>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.</li><br />
<li>On any input, the first qubit has a nonzero probability of being measured 1.</li><br />
</ul><br />
Defined in [[zooref#aar05b|[Aar05b]]], where it is also shown that PostBQP equals [[#pp|PP]].<br />
<br />
[[zooref#aar05b|[Aar05b]]] also gives the following alternate characterizations of PostBQP (and therefore of [[#pp|PP]]):<br />
<ul><br />
<li>The quantum analogue of [[Complexity Zoo:B#bpppath|BPP<sub>path</sub>]].</li><br />
<li>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.</li><br />
<li>The class of problems solvable in quantum polynomial time if we take the probability of measuring a basis state with amplitude &alpha; to be not |&alpha;|<sup>2</sup> but |&alpha;|<sup>p</sup>, 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.)</li><br />
</ul><br />
<br />
----<br />
<br />
===== <span id="pp" style="color:red">PP</span>: Probabilistic Polynomial-Time =====<br />
The class of decision problems solvable by an [[Complexity Zoo:N#np|NP]] machine such that<br />
<ol><br />
<li>If the answer is 'yes' then at least 1/2 of computation paths accept.</li><br />
<li>If the answer is 'no' then less than 1/2 of computation paths accept.</li><br />
</ol><br />
Defined in [[zooref#gil77|[Gil77]]].<br />
<br />
PP is closed under union and intersection [[zooref#brs91|[BRS91]]] (this was an open problem for 14 years).<br />
<br />
Contains [[#pnplog|P<sup>NP[log]</sup>]] [[zooref#bhw89|[BHW89]]].<br />
<br />
Equals PP<sup>[[Complexity Zoo:B#bpp|BPP]]</sup> [[zooref#kst89b|[KST+89b]]] as well as [[#postbqp|PostBQP]] [[zooref#aar05b|[Aar05b]]].<br />
<br />
However, there exists an oracle relative to which PP does not contain [[Complexity Zoo:D#delta2p|&#916;<sub>2</sub>P]] [[zooref#bei94|[Bei94]]].<br />
<br />
[[#ph|PH]] is in [[#ppp2|P<sup>PP</sup>]] [[zooref#tod89|[Tod89]]].<br />
<br />
[[Complexity Zoo:B#bqp|BQP]] is low for PP; i.e. PP<sup>BQP</sup> = PP [[zooref#fr98|[FR98]]].<br />
<br />
For a random oracle A, PP<sup>A</sup> is strictly contained in [[#pspace|PSPACE]]<sup>A</sup> with probability 1 [[zooref#abf94|[ABF+94]]].<br />
<br />
For any fixed k, there exists a language in PP that does not have circuits of size n<sup>k</sup> [[zooref#vin04b|[Vin04b]]]. Indeed, there exists a language in PP that does not even have quantum circuits of size n<sup>k</sup> with quantum advice [[zooref#aar06|[Aar06]]].<br />
<br />
By contrast, there exists an oracle relative to which PP has linear-size circuits [[zooref#aar06|[Aar06]]].<br />
<br />
PP can be generalized to the counting hierarchy [[Complexity Zoo:C#ch|CH]].<br />
<br />
----<br />
<br />
===== <span id="ppcc" style="color:red">PP<sup>cc</sup></span>: Communication Complexity [[#pp|PP]] =====<br />
Defined in [[zooref#bfs86|[BFS86]]], '''PP<sup>cc</sup>''' is one of two ways to define a communication complexity analogue of [[#pp|PP]]. In PP<sup>cc</sup>, we note that in an algorithm that uses an amount of random bits bounded by <math>c</math>, the bias between the accept and reject probabilities can be no smaller than <math>2^c</math>. Thus, in PP<sup>cc</sup>, the communication complexity is defined as the sum of the traditional communication complexity (the number of exchanged bits) and the log of the reciprocal of the worst-case (smallest) bias.<br />
<br />
The difference between this class and [[Complexity Zoo:U#uppcc|UPP<sup>cc</sup>]] is discussed further in [[zooref#bvw07|[BVW07]]], where it is shown that PP<sup>cc</sup> &sub; UPP<sup>cc</sup>.<br />
<br />
The complexity measure corresponding to PP<sup>cc</sup> is equivalent to the "discrepancy bound" [[zooref#kla07|[Kla07]]].<br />
<br />
''See also:'' [[Complexity Zoo:U#uppcc|UPP<sup>cc</sup>]].<br />
----<br />
<br />
===== <span id="pppoly" style="color:red">PP/poly</span>: Nonuniform [[#pp|PP]] =====<br />
Contains [[Complexity Zoo:B#bqpqpoly|BQP/qpoly]] [[zooref#aar04b|[Aar04b]]].<br />
<br />
If PP/poly = [[#ppoly|P/poly]] then [[#pp|PP]] is contained in [[#ppoly|P/poly]]. Indeed this is true with any syntactically defined class in place of [[#pp|PP]]. An implication is that any unrelativized separation of [[Complexity Zoo:B#bqpqpoly|BQP/qpoly]] from [[Complexity Zoo:B#bqpmpoly|BQP/mpoly]] would imply that [[#pp|PP]] does not have polynomial-size circuits.<br />
<br />
----<br />
===== <span id="ppa" style="color:red">PPA</span>: Polynomial Parity Argument =====<br />
Defined in [[zooref#pap94b|[Pap94b]]]; see also [[zooref#bce95|[BCE+95]]].<br />
<br />
The subclass of [[Complexity Zoo:T#tfnp|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."<br />
<br />
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.<br />
<br />
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 [[zooref#pap94|[Pap94]]]). So this problem is in PPA.<br />
<br />
Another problem in PPA is finding an Arrow-Debreu equilibrium, given the goods and utility functions of traders in a marketplace.<br />
<br />
Jeřábek [[zooref#jer12|[Jeř12]]] showed that computing the square root mod n and finding quadratic nonresidues mod n are both in PPA. Further, [[Complexity Garden#integer factorization|integer factorization]] is in PPA under the assumption of a generalized Riemann hypothesis.<br />
<br />
A complete problem for PPA is Sperner's lemma for non-orientable 3-manifolds. [[zooref#gri01|[Gri01]]]<br />
<br />
Contained in [[Complexity Zoo:T#tfnp|TFNP]].<br />
<br />
Contains [[#ppad|PPAD]].<br />
<br />
There exist oracles relative to which PPA does not contain [[#pls|PLS]] [[zooref#bm04|[BM04]]] and [[#ppp|PPP]] [[zooref#bce95|[BCE+95]]]. There also exists an oracle relative to which PPA is not contained in [[#ppp|PPP]] [[zooref#bce95|[BCE+95]]].<br />
<br />
----<br />
<br />
===== <span id="ppad" style="color:red">PPAD</span>: Polynomial Parity Argument (Directed) =====<br />
Defined in [[zooref#pap94b|[Pap94b]]]; see also [[zooref#bce95|[BCE+95]]].<br />
<br />
Same as [[#ppa|PPA]], except now the graph is directed, and we're asked to find either a source or a sink.<br />
<br />
Contained in [[#ppa|PPA]] and [[#ppads|PPADS]].<br />
<br />
NASH, the problem of finding a Nash equilibrium in a normal form game of two or more players with specified utilities, is in PPAD [[zooref#pap94b|[Pap94b]]], and proved to be complete for PPAD with four players in [[zooref#dgp05|[DGP05]]], and shortly after extended to the case of three players [[zooref#dp05|[DP05]]] and independently [[zooref#cd05|[CD05]]].<br />
<br />
There exists an oracle relative to which [[#ppp|PPP]] is not contained in PPAD [[zooref#bce95|[BCE+95]]].<br />
There exists an oracle relative to which PPAD is not contained in [[Complexity Zoo:B#bqp|BQP]] [[zooref#li11|[Li11]]].<br />
<br />
----<br />
<br />
===== <span id="ppads" style="color:red">PPADS</span>: Polynomial Parity Argument (Directed, Sink) =====<br />
Defined in [[zooref#pap94b|[Pap94b]]]; see also [[zooref#bce95|[BCE+95]]].<br />
<br />
Same as [[#ppa|PPA]], except now the graph is directed, and we're asked to find a sink.<br />
<br />
Contained in [[#ppp|PPP]].<br />
<br />
Contains [[#ppad|PPAD]].<br />
<br />
----<br />
===== <span id="ppp" style="color:red">PPP</span>: Polynomial Pigeonhole Principle =====<br />
Defined in [[zooref#pap94b|[Pap94b]]]; see also [[zooref#bce95|[BCE+95]]].<br />
<br />
The subclass of [[Complexity Zoo:T#tfnp|TFNP]] function problems that are guaranteed to have a solution because of the Pigeonhole Principle.<br />
<br />
More precisely, we're given a Boolean circuit, that maps n-bit strings to n-bit strings. The problem is to return <i>either</i> an input that maps to 0<sup>n</sup>, <i>or</i> two inputs that map to the same output.<br />
<br />
Contained in [[Complexity Zoo:T#tfnp|TFNP]].<br />
<br />
Contains [[#ppads|PPADS]].<br />
<br />
[[zooref#bce95|[BCE+95]]] give oracles relative to which PPP is not contained in [[#ppa|PPA]] and [[#ppad|PPAD]], and [[#ppa|PPA]] is not contained in PPP.<br />
<br />
[[zooref#mor01|[Mor01]]] gives an oracle relative to which PPP is not contained in [[#pls|PLS]].<br />
<br />
Whether [[#pls|PLS]] is not contained in PPP relative to some oracle remains open.<br />
<br />
----<br />
===== <span id="ppp2" style="color:red">P<sup>PP</sup></span>: [[#p|P]] With [[#pp|PP]] Oracle =====<br />
A level of the counting hierarchy [[Complexity Zoo:C#ch|CH]].<br />
<br />
It is not known whether there exists an oracle relative to which P<sup>PP</sup> does not equal [[#pspace|PSPACE]].<br />
<br />
Contains [[#pp|PP]]<sup>[[#ph|PH]]</sup> [[zooref#tod89|[Tod89]]].<br />
<br />
Equals [[#psharpp|P<sup>#P</sup>]] (exercise for the visitor).<br />
<br />
Since the permanent of a matrix is [[Complexity Zoo:Symbols#sharpp|#P]]-complete [[zooref#val79|[Val79]]], Toda's theorem implies that any problem in the polynomial hierarchy can be solved by computing a sequence of permanents.<br />
<br />
----<br />
<br />
===== <span id="pqmalog" style="color:red">P<sup>QMA[log]</sup></span>: [[#p|P]] With Log [[Complexity Zoo:Q#qma|QMA]] Queries =====<br />
The class of decision problems solvable by a [[#p|P]] machine, that can make O(log n) queries to a [[Complexity Zoo:Q#qma|QMA]] oracle (where n is the length of the input). <br />
<br />
Defined in [[zooref#amb14|[Amb14]]].<br />
<br />
Equals [[#pparqma|P<sup>||QMA</sup>]] [[zooref#gpy19|[GPY19]]].<br />
<br />
Estimating local observables [[zooref#amb14|[Amb14]]], [[zooref#gy16|[GY16]]] and local correlation functions [[zooref#gy16|[GY16]]] against ground states of local Hamiltonians is P<sup>QMA[log]</sup>-complete.<br />
<br />
Estimating local observables remains P<sup>QMA[log]</sup>-complete even on 2D physical systems and on the 1D line [[zooref#gpy19|[GPY19]]].<br />
<br />
P<sup>QMA[log]</sup> is contained in [[#pp|PP]] [[zooref#gy16|[GY16]]].<br />
<br />
----<br />
<br />
===== <span id="pparqma" style="color:red">P<sup>||QMA</sup></span>: [[#p|P]] With Parallel Queries To [[Complexity Zoo:Q#qma|QMA]] =====<br />
The class of decision problems solvable by a [[#p|P]] machine that can make a polynomial number of non-adaptive queries to a [[Complexity Zoo:Q#qma|QMA]] oracle.<br />
<br />
Equals [[#pqmalog|P<sup>QMA[log]</sup>]] [[zooref#gpy19|[GPY19]]].<br />
<br />
----<br />
<br />
===== <span id="pquery" style="color:red">PQUERY</span>: PSPACE With Polynomial Queries =====<br />
The class of decision problems solvable in polynomial space using at most a polynomial number of queries to the oracle.<br />
<br />
Thus, PQUERY = [[#pspace|PSPACE]], but PQUERY<sup>A</sup> does not equal [[#pspace|PSPACE]]<sup>A</sup> for some oracles A.<br />
<br />
Defined in [[zooref#kur83|[Kur83]]], where it was actually put forward as a serious argument (!!) against believing relativization results.<br />
<!-- TODO: What does the (!!) above mean? --><br />
<br />
----<br />
<br />
===== <span id="ppspace" style="color:red">PPSPACE</span>: Probabilistic [[#pspace|PSPACE]] =====<br />
Same as [[Complexity Zoo:I#ipp|IPP]], except that [[Complexity Zoo:I#ipp|IPP]] uses private coins while PPSPACE uses public coins.<br />
<br />
Can also be defined as a probabilistic version of [[#pspace|PSPACE]].<br />
<br />
Equals [[#pspace|PSPACE]].<br />
<br />
Defined in [[zooref#pap83|[Pap83]]].<br />
<br />
----<br />
===== <span id="pr" style="color:red">PR</span>: Primitive Recursive Functions =====<br />
Basically, the class of functions definable by recursively building up arithmetic functions: addition, multiplication, exponentiation, tetration, etc. What's <i>not</i> 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 [[Complexity Zoo:R#r|R]].<br />
<br />
Alternatively, the PR functions are exactly those functions that can be computed via programs in any reasonable, idealized ALGOL-like programming language where only <i>definite</i> loops are allowed, that is, loops where the number of iterations is specified before the loop starts (so FOR-loops are okay but not WHILE- or REPEAT-loops), and recursive calls are not allowed. <br />
<br />
Alternatively, the PR functions are those functions whose termination can be proved by well-founded induction using an ordinal less than ω<sup>ω</sup>. (There are other systems for higher ordinals. Notably, Gödel's System T is an extension of PR with higher-order functions, and it allows all functions whose termination can be proved by well-founded induction using an ordinal less than ε<sub>0</sub>, including Ackermann's function.)<br />
<br />
An interesting difference is that PR functions can be explicitly enumerated, whereas functions in [[Complexity Zoo:R#r|R]] cannot be (since otherwise the halting problem would be decidable). In this sense, PR is a "syntactic" class whereas [[Complexity Zoo:R#r|R]] is "semantic."<br />
<br />
On the other hand, we can "enumerate" any [[Complexity Zoo:R#re|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.<br />
<br />
PR strictly contains [[Complexity Zoo:E#elementary|ELEMENTARY]].<br />
<br />
----<br />
<br />
===== <span id="pr2" style="color:red">P<sub>R</sub></span>: Polynomial-Time Over The Reals =====<br />
An analog of [[#p|P]] for Turing machines over a real number field.<br />
<br />
Defined in [[zooref#bcs97|[BCS+97]]].<br />
<br />
See also [[#pc|P<sub>C</sub>]], [[Complexity Zoo:N#npc2|NP<sub>C</sub>]], [[Complexity Zoo:N#npr|NP<sub>R</sub>]], [[Complexity Zoo:V#vp|VP<sub>k</sub>]].<br />
<br />
----<br />
===== <span id="prhspace" style="color:red">Pr<sub>H</sub>SPACE(f(n))</span>: Unbounded-Error Halting Probabilistic f(n)-Space =====<br />
Has the same relation to [[Complexity Zoo:D#dspace|DSPACE]](f(n)) as [[#pp|PP]] does to [[#p|P]]. The Turing machine has to halt on every input <i>and</i> every setting of the random tape.<br />
<br />
Equals [[#prspace|PrSPACE]](f(n)) [[zooref#jun85|[Jun85]]].<br />
<br />
----<br />
===== <span id="promisebpp" style="color:red">PromiseBPP</span>: Promise-Problem [[Complexity Zoo:B#bpp|BPP]] =====<br />
Same as [[#promiserp|PromiseRP]], but for [[Complexity Zoo:B#bpp|BPP]] instead of [[Complexity Zoo:R#rp|RP]].<br />
<br />
Defined in [[zooref#bf99|[BF99]]].<br />
<br />
----<br />
===== <span id="promisebqp" style="color:red">PromiseBQP</span>: Promise-Problem [[Complexity Zoo:B#bqp|BQP]] =====<br />
Same as [[#promisebpp|PromiseBPP]], but for [[Complexity Zoo:B#bqp|BQP]] instead of [[Complexity Zoo:B#bpp|BPP]].<br />
<br />
If PromiseBQP = [[#promisep|PromiseP]] then [[Complexity Zoo:B#bqpmpoly|BQP/mpoly]] = [[#ppoly|P/poly]].<br />
<br />
----<br />
<br />
===== <span id="promisep" style="color:red">PromiseP</span>: Promise-Problem [[#p|P]] =====<br />
The class of promise problems solvable by a [[#p|P]] machine.<br />
<br />
----<br />
===== <span id="promiserp" style="color:red">PromiseRP</span>: Promise-Problem [[Complexity Zoo:R#rp|RP]] =====<br />
The class of promise problems solvable by an [[Complexity Zoo:R#rp|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.<br />
<br />
Defined in [[zooref#bf99|[BF99]]], where it was also shown that [[Complexity Zoo:B#bpp|BPP]] is in [[Complexity Zoo:R#rp|RP]]<sup>PromiseRP[1]</sup> (i.e. with a single oracle query to PromiseRP).<br />
<br />
Contained in [[#promisebpp|PromiseBPP]].<br />
<br />
----<br />
<br />
===== <span id="promiseup" style="color:red">PromiseUP</span>: Promise-Problem [[Complexity Zoo:U#up|UP]] =====<br />
The class of promise problems solvable by an [[Complexity Zoo:U#up|UP]] machine. I.e., the nondeterministic machine must have a unique accepting path for "yes" inputs, and no accepting paths "no" inputs, but could have any number of accepting paths for inputs that do not satisfy the promise.<br />
<br />
Although not originally stated with this notation, the main result of [[zooref#vv86|[VV86]]] is that [[Complexity Zoo:N#np|NP]] is contained in [[ComplexityZoo:R#rp|RP]]<sup>PromiseUP</sup>.<br />
<br />
----<br />
<br />
===== <span id="prspace" style="color:red">PrSPACE(f(n))</span>: Unbounded-Error Probabilistic f(n)-Space =====<br />
Has the same relation to [[Complexity Zoo:D#dspace|DSPACE]](f(n)) as [[#pp|PP]] does to [[#p|P]]. The Turing machine has to halt with probability 1 on every input.<br />
<br />
Contained in [[Complexity Zoo:D#dspace|DSPACE]](f(n)<sup>2</sup>) [[zooref#bcp83|[BCP83]]].<br />
<br />
Equals [[#prhspace|Pr<sub>H</sub>SPACE]](f(n)) [[zooref#jun85|[Jun85]]].<br />
<br />
----<br />
===== <span id="psel" style="color:red">P-Sel</span>: P-Selective Sets =====<br />
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.<br />
<br />
Defined in [[zooref#sel79|[Sel79]]], where it was also shown that if [[Complexity Zoo:N#np|NP]] is contained in P-Sel then [[#p|P]] = [[Complexity Zoo:N#np|NP]].<br />
<br />
There exist P-selective sets that are not recursive (i.e. not in [[Complexity Zoo:R#r|R]]).<br />
<br />
----<br />
===== <span id="psk" style="color:red">PSK</span>: Polynomial Sink =====<br />
Yeah, I'm told that's what the S and K stand for. Go figure.<br />
<br />
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.<br />
<br />
Defined in [[zooref#pap90|[Pap90]]].<br />
<br />
Equals [[#ppads|PPADS]].<br />
<br />
----<br />
===== <span id="pspace" style="color:red">PSPACE</span>: Polynomial-Space =====<br />
The class of decision problems solvable by a Turing machine in polynomial space.<br />
<br />
Equals [[Complexity Zoo:N#npspace|NPSPACE]] [[zooref#sav70|[Sav70]]], [[Complexity Zoo:A#ap|AP]] [[zooref#cks81|[CKS81]]], and [[Complexity Zoo:C#czk|CZK]] assuming the existence of one-way functions [[zooref#bgg90|[BGG+90]]].<br />
<br />
Equals [[Complexity Zoo:I#ip|IP]] [[zooref#sha90|[Sha90]]], but PSPACE strictly contains [[#ip|IP]] with probability 1 [[zooref#ccg94|[CCG+94]]].<br />
<br />
Contains [[#psharpp|P<sup>#P</sup>]] ([[#p|P]] with a [[Complexity Zoo:Symbols#sharpp|#P]] oracle).<br />
<br />
A canonical PSPACE-complete problem is [[Complexity_Garden#qbf|QBF]].<br />
<br />
Relative to a random oracle, PSPACE strictly contains [[#ph|PH]] with probability 1 [[zooref#cai86|[Cai86]]].<br />
<br />
PSPACE has a complete problem that is both downward self-reducible and random self-reducible [[zooref#tv02|[TV02]]]. It is the largest class with such a complete problem.<br />
<br />
Contained in [[Complexity Zoo:E#exp|EXP]]. There exists an oracle relative to which this containment is proper [[zooref#dek76|[Dek76]]].<br />
<br />
In descriptive complexity, PSPACE can be defined with 4 differents kind of formulae, [[#Complexity_Zoo:F#fot|FO(<math>2^{n^{O(1)}}</math>)]] which is also [[#Complexity_Zoo:F#fopfp|FO(PFP)]] and [[#Complexity_Zoo:S#fot|SO(<math>n^{O(1)}</math>)]] which is also [[#Complexity_Zoo:F#sotc|SO(TC)]].<br />
----<br />
<br />
===== <span id="pspacecc" style="color:red">PSPACE<sup>cc</sup></span>: Communication Complexity [[#pspace|PSPACE]] =====<br />
<br />
This class is not defined in terms of space, but rather by analogy with the characterization [[Complexity Zoo:P#pspace|PSPACE]]=[[Complexity Zoo:A#ap|AP]]. Specifically, a protocol corresponds to a boolean formula where each leaf represents (the indicator function of) a rectangle; the cost of a protocol is the log of the size of the formula.<br />
<br />
Contains [[Complexity Zoo:P#phcc|PH<sup>cc</sup>]].<br />
<br />
----<br />
<br />
===== <span id="pspacepoly" style="color:red">PSPACE/poly</span>: [[#pspace|PSPACE]] With Polynomial-Size Advice =====<br />
Contains [[Complexity Zoo:Q#qmaqpoly|QMA/qpoly]] [[zooref#aar06b|[Aar06b]]].<br />
<br />
----<br />
<br />
===== <span id="pt1" style="color:red">PT<sub>1</sub></span>: Polynomial Threshold Functions =====<br />
The class of Boolean functions f:{-1,1}<sup>n</sup>->{-1,1} such that f(x)=sgn(p(x)), where p is a polynomial having a number of terms polynomial in n.<br />
<br />
Defined in [[zooref#bs90|[BS90]]], where it was also shown that PT<sub>1</sub> contains [[#pl1|PL<sub>1</sub>]] (and this inclusion is strict), and that PT<sub>1</sub> is contained in [[#plinfinity|PL<sub>&#8734;</sub>]] (and this inclusion is strict).<br />
<br />
----<br />
<br />
===== <span id="ptape" style="color:red">PTAPE</span>: Archaic for [[#pspace|PSPACE]] =====<br />
<br />
----<br />
===== <span id="ptas" style="color:red">PTAS</span>: Polynomial-Time Approximation Scheme =====<br />
The subclass of [[Complexity Zoo:N#npo|NPO]] problems that admit an <i>approximation scheme</i> in the following sense. For any &#949;&gt;0, there is a polynomial-time algorithm that is guaranteed to find a solution whose cost is within a 1+&#949; factor of the optimum cost. (However, the exponent of the polynomial might depend strongly on &#949;.)<br />
<br />
Contains [[Complexity Zoo:F#fptas|FPTAS]], and is contained in [[Complexity Zoo:A#apx|APX]].<br />
<br />
As an example, the Traveling Salesman Problem in the Euclidean plane is in PTAS [[zooref#aro96|[Aro96]]].<br />
<br />
Defined in [[zooref#acg99|[ACG+99]]].<br />
<br />
----<br />
===== <span id="ptwk" style="color:red">PT/WK(f(n),g(n))</span>: Parallel Time f(n) / Work g(n) =====<br />
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).<br />
<br />
The union of PT/WK(log<sup>k</sup>n, n<sup>k</sup>) over all constants k equals [[Complexity Zoo:N#nc|NC]].<br />
<br />
----<br />
===== <span id="pzk" style="color:red">PZK</span>: Perfect Zero Knowledge =====<br />
Same as [[Complexity Zoo:S#szk|SZK]], but now the two distributions must be <i>identical</i>, not merely statistically close. (The "two distributions" are (1) the distribution over the verifier's view of his interaction with the prover, conditioned on the verifier's random coins, and (2) the distribution over views that the verifier can <i>simulate</i> without the prover's help.)<br />
<br />
Contained in [[Complexity Zoo:S#szk|SZK]].<br />
<br />
See also: [[Complexity Zoo:C#czk|CZK]].</div>Atnhttps://complexityzoo.net/index.php?title=Complexity_Zoo:P&diff=6659Complexity Zoo:P2020-04-11T23:02:48Z<p>Atn: /* PSPACE: Polynomial-Space */</p>
<hr />
<div>__NOTOC__<br />
{{CZ-Letter-Menu|P}}<br />
<br />
<br />
===== <span id="p" style="color:red">P</span>: Polynomial-Time =====<br />
The class that started it all.<br />
<br />
The class of decision problems solvable in polynomial time by a Turing machine. (See also [[Complexity Zoo:F#fp|FP]], for function problems.)<br />
<br />
Defined in [[zooref#edm65|[Edm65]]], [[zooref#cob64|[Cob64]]], [[zooref#rab60|[Rab60]]], and other seminal early papers.<br />
<br />
Contains some highly nontrivial problems, including linear programming [[zooref#kha79|[Kha79]]] and finding a maximum matching in a general graph [[zooref#edm65|[Edm65]]].<br />
<br />
Contains the problem of testing whether an integer is prime [[zooref#aks02|[AKS02]]], an important result that improved on a proof requiring an assumption of the generalized Riemann hypothesis [[zooref#mil76|[Mil76]]].<br />
<br />
A decision problem is P-complete if it is in P, and if every problem in P can be reduced to it in [[Complexity Zoo:L#l|L]] (logarithmic space). The canonical P-complete problem is <i>circuit evaluation</i>: given a Boolean circuit and an input, decide what the circuit outputs when given the input.<br />
<br />
Important subclasses of P include [[Complexity Zoo:L#l|L]], [[Complexity Zoo:N#nl|NL]], [[Complexity Zoo:N#nc|NC]], and [[Complexity Zoo:S#sc|SC]].<br />
<br />
P is contained in [[Complexity Zoo:N#np|NP]], but whether they're equal seemed to be an open problem when I last checked.<br />
<br />
Efforts to generalize P resulted in [[Complexity Zoo:B#bpp|BPP]] and [[Complexity Zoo:B#bqp|BQP]].<br />
<br />
The nonuniform version is [[#ppoly|P/poly]], the monotone version is [[Complexity Zoo:M#mp|mP]], and versions over the real and complex number fields are [[#pr2|P<sub>R</sub>]] and [[#pc|P<sub>C</sub>]] respectively.<br />
<br />
In descriptive complexity, P can be defined by three different kind of formulae, [[#Complexity_Zoo:F#folfp|FO(lfp)]] which is also [[#Complexity_Zoo:F#fot|FO(<math>n^{O(1)}</math>)]]], and also as [[#Complexity_Zoo:S#sohorn|SO(Horn)]]<br />
<br />
P queries are exactly the one that can be written in the [[#Complexity_Zoo:S#while|While<sup>/cons</sup>]] languages.<br />
<br />
P is the class of decision problems solvable by a (logspace) ''uniform'' family of polynomial-size Boolean circuits.<br />
----<br />
<br />
===== <span id="plog" style="color:red">P/log</span>: [[#p|P]] With Logarithmic Advice =====<br />
Same as [[#ppoly|P/poly]], except that the advice string for input size n can have length at most logarithmic in n, rather than polynomial.<br />
<br />
Strictly contained in [[Complexity Zoo:I#iclogpoly|IC[log,poly]]].<br />
<br />
If [[Complexity Zoo:N#np|NP]] is contained in P/log then [[#p|P]] = [[Complexity Zoo:N#np|NP]].<br />
<br />
----<br />
===== <span id="ppoly" style="color:red">P/poly</span>: Nonuniform Polynomial-Time =====<br />
The class of decision problems solvable by a family of polynomial-size Boolean circuits. The family can be <i>nonuniform</i>; that is, there could be a completely different circuit for each input length.<br />
<br />
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.<br />
<br />
Contains [[Complexity Zoo:B#bpp|BPP]] by the progenitor of derandomization arguments [[zooref#adl78|[Adl78]]] [[zooref#kl82|[KL82]]]. By extension, BPP/poly, BPP/mpoly, and BPP/rpoly all equal P/poly. (By contrast, there is an oracle relative to which [[Complexity Zoo:B#bpplog|BPP/log]] does not equal [[Complexity Zoo:B#bppmlog|BPP/mlog]], while [[Complexity Zoo:B#bppmlog|BPP/mlog]] and [[Complexity Zoo:B#bpprlog|BPP/rlog]] are not equal relative to any oracle.)<br />
<br />
[[zooref#kl82|[KL82]]] showed that, if P/poly contains [[Complexity Zoo:N#np|NP]], then [[#ph|PH]] collapses to the second level, [[Complexity Zoo:S#sigma2p|&#931;<sub>2</sub>P]].<br />
<br />
They also showed:<br />
<ul><br />
<li>If [[#pspace|PSPACE]] is in P/poly then [[#pspace|PSPACE]] equals [[Complexity Zoo:S#sigma2p|&#931;<sub>2</sub>P]] &#8745; [[#pi2p|&#928;<sub>2</sub>P]].</li><br />
<li>If [[Complexity Zoo:E#exp|EXP]] is in P/poly then [[Complexity Zoo:E#exp|EXP]] = [[Complexity Zoo:S#sigma2p|&#931;<sub>2</sub>P]].</li><br />
</ul><br />
It was later shown that, if [[Complexity Zoo:N#np|NP]] is contained in P/poly, then [[#ph|PH]] collapses to [[Complexity Zoo:Z#zpp|ZPP]]<sup>[[Complexity Zoo:N#np|NP]]</sup> [[zooref#kw98|[KW98]]] and indeed [[Complexity Zoo:S#s2p|S<sub>2</sub>P]] [[zooref#cai01|[Cai01]]]. This seems close to optimal, since there exists an oracle relative to which the collapse cannot be improved to [[Complexity Zoo:D#delta2p|&#916;<sub>2</sub>P]] [[zooref#wil85|[Wil85]]].<br />
<br />
If [[Complexity Zoo:N#np|NP]] is not contained in P/poly, then [[#p|P]] does not equal [[Complexity Zoo:N#np|NP]]. Much of the effort toward separating [[#p|P]] from [[Complexity Zoo:N#np|NP]] is based on this observation. However, a 'natural proof' as defined by [[zooref#rr97|[RR97]]] cannot be used to show [[Complexity Zoo:N#np|NP]] is outside P/poly, if there is any pseudorandom generator in P/poly that has hardness 2<sup>&#937;(n^&#949;)</sup> for some &#949;&gt;0.<br />
<br />
If [[Complexity Zoo:N#np|NP]] is contained in P/poly, then [[Complexity Zoo:M#ma|MA]] = [[Complexity Zoo:A#am|AM]] [[zooref#aks95|[AKS+95]]]<br />
<br />
The monotone version of P/poly is [[Complexity Zoo:M#mppoly|mP/poly]].<br />
<br />
P/poly has measure 0 in [[Complexity Zoo:E#e|E]] with [[Complexity Zoo:S#sigma2p|&#931;<sub>2</sub>P]] oracle [[zooref#may94b|[May94b]]].<br />
<br />
Strictly contains [[Complexity Zoo:I#iclogpoly|IC[log,poly]]] and [[#plog|P/log]].<br />
<br />
----<br />
<br />
===== <span id="psharpp" style="color:red">P<sup>#P</sup></span>: [[#p|P]] With [[Complexity Zoo:Symbols#sharpp|#P]] Oracle =====<br />
I decided this class is so important that it deserves an entry of its own, apart from [[Complexity Zoo:Symbols#sharpp|#P]].<br />
<br />
Contains [[#ph|PH]] [[zooref#tod89|[Tod89]]], and is contained in [[#pspace|PSPACE]].<br />
<br />
Equals [[#ppp2|P<sup>PP</sup>]] (exercise for the visitor).<br />
<br />
----<br />
===== <span id="psharpp1" style="color:red">P<sup>#P[1]</sup></span>: [[#p|P]] With Single Query To [[Complexity Zoo:Symbols#sharpp|#P]] Oracle =====<br />
Contains [[#ph|PH]] [[zooref#tod89|[Tod89]]].<br />
<br />
----<br />
===== <span id="pctc" style="color:red">P<sub>CTC</sub></span>: [[#p|P]] With Closed Time Curves =====<br />
Same as [[#p|P]] with access to bits along a closed time curve.<br />
<br />
Implicitly defined in [[zooref#aar05c|[Aar05c]]], where it was shown that PSPACE = P<sub>CTC</sub>.<br />
<br />
See also [[Complexity Zoo:B#bqpctc|BQP<sub>CTC</sub>]].<br />
<br />
----<br />
===== <span id="para" style="color:red">para-</span>: Parameterized Complexity =====<br />
The para- prefix indicates that a complexity class is parameterized by some other measure of complexity. Specifically, a language L is in the parameterized class para-C, if there is an alphabet A and a computable function pi(k) -> A*, such that every (Q,k) is in para-L if and only if (Q,pi(k)) in L.<br />
<br />
The prototypical example (as well the violation of the naming convention) is para-P, which is almost always known as [[Complexity Zoo:FPT#fpt|FPT]], which is equal to DTIME(f(k)n^c) for some constant c.<br />
<br />
Space-parameterized examples include [[#para-L|para-L]] and [[#para-NL|para-NL]], which are equal to DSPACE(f(k)+log(n)) and NDSPACE(f(k)+log(n)), respectively.<br />
<br />
Compare with the slicewise complexity classes [[Complexity Zoo:X#x|X-]], such as [[Complexity Zoo:X#x|X-]].<br />
<br />
Discussed in:<br />
J. Flum and M. Grohe. Describing parameterized complexity classes. Information and Computation.<br />
and<br />
Elberfeld M., Stockhusen C., Tantau T. (2012) On the Space Complexity of Parameterized Problems.<br />
<br />
----<br />
===== <span id="paral" style="color:red">para-L</span>: Parameterized Logspace =====<br />
[[#para|para-]] version of [[Complexity Zoo:L#l|L]]. Equivalent to DSPACE(f(k)+log(n)) for some computable function f. Compare with slicewise parameterized logspace, [[Complexity Zoo:X#xl|XL]].<br />
<br />
Parameterized vertex cover (is there a vertex cover of size at most k) is complete for para-L. (Elberfeld et al, 2012)<br />
<br />
----<br />
===== <span id="paranl" style="color:red">para-NL</span>: Parameterized Nondeterministic Logspace =====<br />
[[#para|para-]] version of [[Complexity Zoo:N#nl|NL]]. Equivalent to NDSPACE(f(k)+log(n)) for some computable function f. Compare with slicewise parameterized nondeterministic logspace, [[Complexity Zoo:X#xnl|XNL]].<br />
<br />
It seems open whether there are natural complete problems for para-NL. However, the related class [[#paranlflog|para-NL[f log]]] has many natural complete problems.<br />
<br />
----<br />
===== <span id="paranlflog" style="color:red">para-NL[f log]</span>: Parameterized Nondeterministic Logspace =====<br />
Like [[#paranl|para-NL]], but where the number of nondeterministic branches is bounded by O(f(k) log(n)).<br />
<br />
A natural complete is problem parameterized distance: is there a path on directed graph G from vertex s to v, of length at most k? (Elberfeld et al, 2012)<br />
<br />
para-NL[f log] is contained within [[Complexity Zoo:X#xl|XL]], slicewise logspace.<br />
<br />
----<br />
===== <span id="parap" style="color:red">para-P</span>: Parameterized Polynomial time. =====<br />
para-P is a less common name for [[Complexity Zoo:F#fpt|FPT]], but in line with other [[#para|para-]] classes naming conventions. Its slicewise counterpart is still called [[Complexity Zoo:X#xp|XP]].<br />
----<br />
<br />
===== <span id="pac0" style="color:red">PAC<sup>0</sup></span>: Probabilistic [[Complexity Zoo:A#ac0|AC<sup>0</sup>]] =====<br />
The Political Action Committee for computational complexity research.<br />
<br />
The class of problems for which there exists a [[Complexity Zoo:D#diffac0|DiffAC<sup>0</sup>]] function f such that the answer is "yes" on input x if and only if f(x)>0.<br />
<br />
Equals [[Complexity Zoo:T#tc0|TC<sup>0</sup>]] and [[Complexity Zoo:C#cequalsac0|C<sub>=</sub>AC<sup>0</sup>]] under logspace uniformity [[zooref#abl98|[ABL98]]].<br />
<br />
----<br />
===== <span id="pbp" style="color:red">PBP</span>: Polynomial-Size Branching Program =====<br />
Same as [[#kpbp|k-PBP]] but with no width restriction.<br />
<br />
Equals [[Complexity Zoo:L#l/poly|L/poly]] [[zooref#cob66|[Cob66]]].<br />
<br />
Contains [[#pobdd|P-OBDD]], [[Complexity Zoo:B#bpdp|BP<sub>d</sub>(P)]].<br />
<br />
----<br />
<br />
===== <span id="kpbp" style="color:red">k-PBP</span>: Polynomial-Size Width-k Branching Program =====<br />
A <i>branching program</i> 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.<br />
<br />
The <i>size</i> of the branching program is the number of vertices. The branching program has <i>width k</i> 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.<br />
<br />
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.)<br />
<br />
k-PBP equals (nonuniform) [[Complexity Zoo:N#nc1|NC<sup>1</sup>]] for constant k at least 5 [[zooref#bar89|[Bar89]]]. On the other hand, 4-PBP is in [[Complexity Zoo:A#acc0|ACC<sup>0</sup>]] [[zooref#bt88|[BT88]]].<br />
<br />
Contained in k-[[Complexity Zoo:E#eqbp|EQBP]], as well as [[#pbp|PBP]].<br />
<br />
See also [[Complexity Zoo:B#bpdp|BP<sub>d</sub>(P)]].<br />
----<br />
<br />
===== <span id="pc" style="color:red">P<sub>C</sub></span>: Polynomial-Time Over The Complex Numbers =====<br />
An analog of [[#p|P]] for Turing machines over a complex number field.<br />
<br />
Defined in [[zooref#bcs97|[BCS+97]]].<br />
<br />
See also [[#pr2|P<sub>R</sub>]], [[Complexity Zoo:N#npc2|NP<sub>C</sub>]], [[Complexity Zoo:N#npr|NP<sub>R</sub>]], [[Complexity Zoo:V#vp|VP<sub>k</sub>]].<br />
<br />
----<br />
===== <span id="pcc" style="color:red">P<sup>cc</sup></span>: Communication Complexity [[#p|P]] =====<br />
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<sup>cc</sup> 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.<br />
<br />
Note that all functions of the form above are solvable given <math>O(n)</math> bits of communication, since no bounds are placed on the computational abilities of Alice and Bob. Thus, when discussing this class, "polynomially" is sometimes used in place of "polylogarithmically."<br />
<br />
Is strictly contained in [[Complexity Zoo:N#npcc|NP<sup>cc</sup>]] and in [[Complexity Zoo:B#bppcc|BPP<sup>cc</sup>]] because of the [[Complexity Garden#equality|EQUALITY]] problem.<br />
<br />
If the classes are defined in terms of total functions, then P<sup>cc</sup> = [[Complexity Zoo:N#npcc|NP<sup>cc</sup>]] &#8745; [[Complexity Zoo:N#npcc|coNP<sup>cc</sup>]] = [[Complexity Zoo:U#upcc|UP<sup>cc</sup>]].<br />
<br />
Defined in [[zooref#bfs86|[BFS86]]].<br />
<br />
----<br />
<br />
===== <span id="pkcc" style="color:red">P<sub><math>k</math></sub><sup>cc</sup></span>: [[#pcc|P<sup>cc</sup>]] in NOF model, <math>k</math> players =====<br />
<br />
Like [[#pcc|P<sup>cc</sup>]], but with <math>k</math> players, where each player can see all of the other player's bits, but not their own. Intuitively, each player has their bits written on their forehead.<br />
<br />
More formally, P<sub><math>k</math></sub><sup>cc</sup> is the class of functions <math>F:X_1\times X_2 \times \cdots \times X_k \to \{0,1\}</math> where for all <math>i\in[1..k]</math>, <math>X_k\in\{0,1\}^n</math>, such that <math>F</math> is solvable in a deterministic sense by <math>k</math> players, each of which is aware of all inputs <math>X_i</math> other than his own, and such that <math>O\left(\mathrm{poly}(\log n)\right)</math> bits of communication are used.<br />
<br />
P<sub><math>k</math></sub><sup>cc</sup> is trivially contained in {{zcls|b|bppkcc|BPP<sub><math>k</math></sub><sup>cc</sup>}}, {{zcls|r|rpkcc|RP<sub><math>k</math></sub><sup>cc</sup>}} and {{zcls|n|npkcc|NP<sub><math>k</math></sub><sup>cc</sup>}}.<br />
<br />
----<br />
<br />
===== <span id="pcd" style="color:red">PCD(r(n),q(n))</span>: Probabilistically Checkable Debate =====<br />
The class of decision problems decidable by a <i>probabilistically checkable debate system</i>, as follows.<br />
<br />
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)) <i>nonadaptive</i> 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.<br />
<br />
Defined in [[zooref#cfl93|[CFL+93]]], who also showed that PCD(log n, 1) = [[#pspace|PSPACE]]. This result was used to show that certain problems are [[#pspace|PSPACE]]-hard even to approximate.<br />
<br />
Contained in [[Complexity Zoo:G#gpcd|GPCD]](r(n),q(n)).<br />
<br />
----<br />
===== <span id="pclose" style="color:red">P-Close</span>: Problems Close to [[#p|P]] =====<br />
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.<br />
<br />
Defined in [[zooref#yes83|[Yes83]]].<br />
<br />
Contains [[Complexity Zoo:A#almostp|Almost-P]] and is contained in [[#ppoly|P/poly]] [[zooref#sch86|[Sch86]]].<br />
<br />
----<br />
<br />
===== <span id="pcp" style="color:red">PCP(r(n),q(n))</span>: Probabilistically Checkable Proof =====<br />
The class of decision problems such that a "yes" answer can be verified by a <i>probabilistically checkable proof</i>, as follows.<br />
<br />
The verifier is a polynomial-time Turing machine with access to O(r(n)) uniformly random bits. It has random access to a <i>proof</i> (which might be exponentially long), but can query only O(q(n)) bits of the proof.<br />
<br />
Then we require the following:<br />
<ol><br />
<li>If the answer is "yes," there exists a proof such that the verifier accepts with certainty.</li><br />
<li>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).</li><br />
</ol><br />
Defined in [[zooref#as98|[AS98]]].<br />
<br />
By definition [[Complexity Zoo:N#np|NP]] = PCP(0,poly(n)).<br />
<br />
[[Complexity Zoo:M#mip|MIP]] = PCP(poly(n),poly(n)).<br />
<br />
PCP(r(n),q(n)) is contained in [[Complexity Zoo:N#ntime|NTIME]](2<sup>O(r(n))</sup>q(n) + poly(n)).<br />
<br />
[[Complexity Zoo:N#np|NP]] = PCP(log n, log n) [[zooref#as98|[AS98]]].<br />
<br />
In fact, [[Complexity Zoo:N#np|NP]] = PCP(log n, 1) [[zooref#alm98|[ALM+98]]]!<br />
<br />
On the other hand, if [[Complexity Zoo:N#np|NP]] is contained in PCP(o(log n), o(log n)), then [[#p|P]] = [[Complexity Zoo:N#np|NP]] [[zooref#fgl91|[FGL+91]]].<br />
<br />
Also, even though there exists an oracle relative to which [[Complexity Zoo:N#np|NP]] = [[Complexity Zoo:E#exp|EXP]] [[zooref#hel84|[Hel84]]], if we could show there exists an oracle relative to which PCP(log n, 1) = [[Complexity Zoo:E#exp|EXP]], then we'd have proved [[#p|P]] not equal to [[Complexity Zoo:N#np|NP]] [[zooref#for94|[For94]]].<br />
<br />
Another weird oracle fact: since [[Complexity Zoo:N#np|NP]] does not equal [[Complexity Zoo:N#nexp|NEXP]] [[zooref#sfm78|[SFM78]]], PCP(log n, log n) does not equal PCP(poly(n), poly(n)). However, there exist oracles relative to which the latter inequality is false [[zooref#hcc92|[HCC+92]]].<br />
<br />
----<br />
===== <span id="pdqp" style="color:red">PDQP</span>: Product Dynamical Quantum Polynomial time =====<br />
<br />
This class is a generalization of [[Complexity Zoo:B#bqp|BQP]] where one is allowed to perform measuresments without collapsing the wavefunction.[[zooref#abfl14|[ABFL14]]]<br />
<br />
Unlike, BQP this is likely to be a not physically realizable class.<br />
<br />
Contains [[Complexity Zoo:S#szk|SZK]] and thus contains graph isomorphism.<br />
<br />
There is an oracle relative to which BQP is not equal to PDQP and an oracle relative to which NP is not contained in PDQP. <br />
<br />
PDQP can perform unordered searches faster than BQP. <br />
<br />
Compare [[Complexity Zoo:D#DQP|DQP]]. <br />
----<br />
<br />
===== <span id="permup" style="color:red">PermUP</span>: Self-Permuting [[Complexity Zoo:U#up|UP]] =====<br />
The class of languages L in [[Complexity Zoo:U#up|UP]] such that the mapping from an input x to the unique witness for x is a permutation of L.<br />
<br />
Contains [[#p|P]].<br />
<br />
Defined in [[zooref#ht03|[HT03]]], where it was also shown that the closure of PermUP under polynomial-time one-to-one reductions is [[Complexity Zoo:U#up|UP]].<br />
<br />
On the other hand, they show that if PermUP = [[Complexity Zoo:U#up|UP]] then [[Complexity Zoo:E#e|E]] = [[Complexity Zoo:U#ue|UE]].<br />
<br />
See also: [[Complexity Zoo:S#selfnp|SelfNP]].<br />
<br />
----<br />
===== <span id="pexp" style="color:red">PEXP</span>: Probabilistic Exponential-Time =====<br />
Has the same relation to [[Complexity Zoo:E#exp|EXP]] as [[#pp|PP]] does to [[#p|P]].<br />
<br />
Is not contained in [[#ppoly|P/poly]] [[zooref#bft98|[BFT98]]].<br />
<br />
----<br />
===== <span id="pf" style="color:red">PF</span>: Alternate Name for [[Complexity Zoo:F#fp|FP]] =====<br />
<br />
----<br />
===== <span id="pfchk" style="color:red">PFCHK(t(n))</span>: Proof-Checker =====<br />
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 <i>proof string</i> of unbounded length.<br />
<ul><br />
<li>If the answer is "yes," then there exists a value of the proof string such that all computation paths accept.</li><br />
<li>If the answer is "no," then for all values of the proof string, there exists a computation path that rejects.</li><br />
</ul><br />
Credited in [[zooref#for94|[For94]]] to S. Arora, R. Impagliazzo, and U. Vazirani.<br />
<br />
An interesting question is whether [[Complexity Zoo:N#np|NP]] = PFCHK(log n) relative to all possible oracles. Fortnow [[zooref#for94|[For94]]] observes that the answer depends on what oracle access mechanism is used.<br />
<br />
----<br />
===== <span id="ph" style="color:red">PH</span>: Polynomial-Time Hierarchy =====<br />
Let &#916;<sub>0</sub>P = &#931;<sub>0</sub>P = &#928;<sub>0</sub>P = [[#p|P]]. Then for i&gt;0, let<br />
<ul><br />
<li>&#916;<sub>i</sub>P = [[#p|P]] with &#931;<sub>i-1</sub>P oracle.</li><br />
<li>&#931;<sub>i</sub>P = [[Complexity Zoo:N#np|NP]] with &#931;<sub>i-1</sub>P oracle.</li><br />
<li>&#928;<sub>i</sub>P = [[Complexity Zoo:C#conp|coNP]] with &#931;<sub>i-1</sub>P oracle.</li><br />
</ul><br />
Then PH is the union of these classes for all nonnegative constant i.<br />
<br />
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 &phi;(x,y,z,w,...)," where y,z,w,... are polynomial-size strings and &phi; 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 [[Complexity Zoo:N#np|NP]] oracle queries and the second one doesn't, but it is.<br />
<br />
Defined in [[zooref#sto76|[Sto76]]].<br />
<br />
Contained in [[#p|P]] with a [[#pp|PP]] oracle [[zooref#tod89|[Tod89]]].<br />
<br />
Contains [[Complexity Zoo:B#bpp|BPP]] [[zooref#lau83|[Lau83]]].<br />
<br />
Relative to a random oracle, PH is strictly contained in [[#pspace|PSPACE]] with probability 1 [[zooref#cai86|[Cai86]]].<br />
<br />
Furthermore, there exist oracles separating any &#931;<sub>i</sub>P from &#931;<sub>i+1</sub>P. In fact, relative to a random oracle, the hierarchy is infinite: each level is strictly contained in the next, with probability 1 [[zooref#rst15|[RST15]]] (this was an open problem for 29 years). Previously, it had been known that if it had collapsed relative to a random oracle, then it would have collapsed unrelativized [[zooref#boo94|[Boo94]]].<br />
<br />
It was shown in [[zooref#cp07|[CPO7]]] that if the NP Machine Hypothesis holds, then<br />
<math><br />
\mathsf{P}^{\mathrm{SAT}[1]} = \mathsf{P}^{\mathrm{SAT}[2]} \Rightarrow \mathsf{PH} \subseteq \mathsf{NP}<br />
</math>.<br />
<br />
For a compendium of problems complete for different classes of the Polynomial Hierarchy see [[zooref#sch02a|[Sch02a]]] and [[zooref#sch02b|[Sch02b]]].<br />
<br />
PH is equal to the set of boolean queries recognizable by a concurent random acess machine using exponentially many processors and constant time[[zooref#imm89|[Imm89]]].<br />
<br />
Since NP is the class of query expressible in second-order existantial logic, PH can also be defined as the query expressible in [[#Complexity_Zoo:S#so|second-order logic]].<br />
----<br />
<br />
===== <span id="phcc" style="color:red">PH<sup>cc</sup></span>: Communication Complexity [[#ph|PH]] =====<br />
The polynomial hierarchy for communication complexity, naturally built with [[Complexity Zoo:N#npcc|NP<sup>cc</sup>]] and [[Complexity Zoo:C#conpcc|coNP<sup>cc</sup>]] forming the first level. Specifically, a cost-k protocol in the PH<sup>cc</sup> model corresponds to a constant-depth 2<sup>k</sup>-ary tree whose internal nodes are alternating layers of AND and OR gates, and whose leaves represent (the indicator functions of) either rectangles or complements of rectangles, as appropriate.<br />
<br />
It is unknown whether &#931;<sub>2</sub><sup>cc</sup> equals &#928;<sub>2</sub><sup>cc</sup>.<br />
<br />
Defined in [[zooref#bfs86|[BFS86]]], where it was also shown (among other things) that [[Complexity Zoo:B#bppcc|BPP<sup>cc</sup>]] is contained in &#931;<sub>2</sub><sup>cc</sup> &#8745; &#928;<sub>2</sub><sup>cc</sup>.<br />
<br />
----<br />
<br />
===== <span id="phi2p" style="color:red">&#934;<sub>2</sub>P</span>: Second Level of the Symmetric Hierarchy, Alternative Definition =====<br />
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<br />
<ol><br />
<li>For all y, there exists a z for which P(x,y,z).</li><br />
<li>For all z, there exists a y for which P(x,y,z).</li><br />
</ol><br />
Contained in [[Complexity Zoo:S#sigma2p|&#931;<sub>2</sub>P]] and [[#pi2p|&#928;<sub>2</sub>P]].<br />
<br />
Defined in [[zooref#can96|[Can96]]], where it was also observed that &#934;<sub>2</sub>P = [[Complexity Zoo:S#s2p|S<sub>2</sub>P]].<br />
<br />
----<br />
===== <span id="php" style="color:red">PhP</span>: Physical Polynomial-Time =====<br />
Defined by Valiant [[zooref#val03|[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|P]] and [[Complexity Zoo:B#bpp|BPP]], but that it is open whether PhP contains [[Complexity Zoo:B#bqp|BQP]], since no scalable quantum computing proposal has been demonstrated beyond reasonable doubt.<br />
<br />
For what it's worth, the present zookeeper has more qualms about admitting [[Complexity Zoo:D#dtime|DTIME]](n<sup>1000</sup>) into PhP than [[Complexity Zoo:B#bqtime|BQTIME]](n<sup>2</sup>). 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<sup>k</sup> with k in the low hundreds.) In practice, less than 10<sup>50</sup> bits and less than 10<sup>80</sup> 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.)<br />
<br />
The present veterinarian concurs that PhP is an unhealthy animal, although it is valid to ask whether [[Complexity Zoo:B#bqp|BQP]] is a realistic class.<br />
<br />
----<br />
<br />
===== <span id="pi2p" style="color:red">&#928;<sub>2</sub>P</span>: [[Complexity Zoo:C#conp|coNP]] With [[Complexity Zoo:N#np|NP]] Oracle =====<br />
Complement of [[Complexity Zoo:S#sigma2p|&#931;<sub>2</sub>P]].<br />
<br />
Along with [[Complexity Zoo:S#sigma2p|&#931;<sub>2</sub>P]], comprises the second level of [[#ph|PH]], the polynomial hierarchy. For any fixed k, there is a problem in &#928;<sub>2</sub>P &#8745; [[Complexity Zoo:S#sigma2p|&#931;<sub>2</sub>P]] that cannot be solved by circuits of size n<sup>k</sup> [[zooref#kan82|[Kan82]]].<br />
<br />
----<br />
===== <span id="pinc" style="color:red">PINC</span>: Polynomial Ignorance of Names of Classes =====<br />
(Actually, I've since been informed that PINC means "Incremental Polynomial-Time.")<br />
<br />
The class of function problems, f:{0,1}<sup>n</sup>-&gt;{0,1}<sup>m</sup>, such that the k<sup>th</sup> output bit is computable in time polynomial in n and k.<br />
<br />
Defined in [[zooref#jy88|[JY88]]].<br />
<br />
Contained in [[#pio|PIO]]. This containment is strict, since if m=2<sup>n</sup> (say), then computing the first bit of f(x) might be [[Complexity Zoo:E#exp|EXP]]-complete.<br />
<br />
----<br />
===== <span id="pio" style="color:red">PIO</span>: Polynomial Input Output =====<br />
The class of function problems, f:{0,1}<sup>n</sup>-&gt;{0,1}<sup>m</sup>, 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.<br />
<br />
Defined in [[zooref#yan81|[Yan81]]].<br />
<br />
Strictly contains [[#pinc|PINC]].<br />
<br />
----<br />
===== <span id="pk" style="color:red">P<sup>K</sup></span>: [[#p|P]] With Kolmogorov-Complexity Oracle =====<br />
[[#p|P]] equipped with an oracle that, given a string x, returns the length of the shortest program that outputs x.<br />
<br />
A similar class was defined in [[zooref#abk02|[ABK+02]]], where it was also shown that P<sup>K</sup> contains [[#pspace|PSPACE]]. It is not known whether P<sup>K</sup> contains all of [[Complexity Zoo:R#r|R]], or even any recursive problem not in [[#pspace|PSPACE]].<br />
<br />
See also: [[Complexity Zoo:B#bppkt|BPP<sup>KT</sup>]].<br />
<br />
----<br />
===== <span id="pkc" style="color:red">PKC</span>: Perfect Knowledge Complexity =====<br />
Has the same relation to [[#pzk|PZK]] as [[#skc|SKC]] does to [[Complexity Zoo:S#szk|SZK]].<br />
<br />
Defined in [[zooref#gp91|[GP91]]].<br />
<br />
----<br />
===== <span id="pl" style="color:red">PL</span>: Probabilistic [[Complexity Zoo:L#l|L]] =====<br />
Has the same relation to [[Complexity Zoo:L#l|L]] that [[#pp|PP]] has to [[#p|P]].<br />
<br />
Contains [[Complexity Zoo:B#bpl|BPL]].<br />
<br />
PL<sup>PL</sup> = PL (see [[zooref#ho02|[HO02]]]).<br />
<br />
----<br />
===== <span id="pl1" style="color:red">PL<sub>1</sub></span>: Polynomially-Bounded L<sub>1</sub> Spectral Norm =====<br />
The class of Boolean functions f:{-1,1}<sup>n</sup>->{-1,1} such that the sum of absolute values of Fourier coefficients of f is bounded by a polynomial in n.<br />
<br />
Defined in [[zooref#bs90|[BS90]]], where it was also shown that PL<sub>1</sub> is contained in [[#pt1|PT<sub>1</sub>]] (and this inclusion is strict).<br />
<br />
----<br />
===== <span id="plinfinity" style="color:red">PL<sub>&#8734;</sub></span>: Polynomially-Bounded L<sub>&#8734;</sub><sup>-1</sup> Spectral Norm =====<br />
The class of Boolean functions f:{-1,1}<sup>n</sup>->{-1,1} such that the maximum of |&alpha;|<sup>-1</sup>, over all Fourier coefficients &alpha; of f, is upper-bounded by a polynomial in n.<br />
<br />
Defined in [[zooref#bs90|[BS90]]], where it was also shown that PL<sub>&#8734;</sub> contains [[#pt1|PT<sub>1</sub>]] (and this inclusion is strict).<br />
<br />
----<br />
<br />
===== <span id="plf" style="color:red">PLF</span>: Polynomial Leaf =====<br />
Defined in [[zooref#pap90|[Pap90]]].<br />
<br />
I believe it's the same as [[#ppa|PPA]].<br />
<br />
----<br />
===== <span id="pll" style="color:red">PLL</span>: Polynomial Local Lemma =====<br />
The class of [[Complexity Zoo:T#tfnp|TFNP]] function problems that are guaranteed to have a solution because of the Lov&aacute;sz Local Lemma. Defined in [[zooref#pap94b|[Pap94b]]].<br />
<br />
----<br />
===== <span id="pls" style="color:red">PLS</span>: Polynomial Local Search =====<br />
The subclass of [[Complexity Zoo:T#tfnp|TFNP]] function problems that are guaranteed to have a solution because of the lemma that "every finite directed acyclic graph has a sink."<br />
<br />
More precisely, for each input, there's a finite set of <i>solutions</i> (i.e. strings), and a polynomial-time algorithm that computes a <i>cost</i> for each solution, and a <i>neighboring solution</i> 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.)<br />
<br />
(<i>Note:</i> In the Zookeeper's humble opinion, PLS <i>should</i> have been defined as follows: there exist polynomial-time algorithms that compute the cost of a solution, and the set of <i>all</i> 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.)<br />
<br />
(<i>Note to Note:</i> The equivalance of these classes was shown (though not stated explicitly) in Theorem 1 of [[zooref#jpy88|[JPY88]]].) <!-- by Domotor Palvolgyi--><br />
<br />
Defined in [[zooref#jpy88|[JPY88]]], [[zooref#py88|[PY88]]].<br />
<br />
There exists an oracle relative to which PLS is not contained in [[Complexity Zoo:F#fbqp|FBQP]] [[zooref#aar03|[Aar03]]].<br />
<br />
Also, there exist oracles relative to which PLS is not contained in [[#ppa|PPA]] [[zooref#bm04|[BM04]]], and [[#ppa|PPA]] and [[#ppp|PPP]] are not contained in PLS [[zooref#mor01|[Mor01]]].<br />
<br />
Whether PLS is not in [[#ppp|PPP]] relative to some oracle remains open.<br />
<br />
[[zooref#ct07|[CT07]]] conjecture that if [[#ppad|PPAD]] is in [[#p|P]], then [[#pls|PLS]] is in [[#p|P]].<br />
----<br />
<br />
===== <span id="pnp" style="color:red">P<sup>NP</sup></span>: [[#p|P]] With Oracle Access To [[Complexity Zoo:N#np|NP]] =====<br />
See [[Complexity Zoo:D#delta2p|&#916;<sub>2</sub>P]].<br />
<br />
----<br />
<br />
===== <span id="pnpcc" style="color:red">P<sup>NPcc</sup></span>: Communication Complexity [[#pnp|P<sup>NP</sup>]] =====<br />
<br />
Not contained in [[Complexity Zoo:P#ppcc|PP<sup>cc</sup>]] [[zooref#bvw07|[BVW07]]].<br />
<br />
Does not contain [[Complexity Zoo:B#bppcc|BPP<sup>cc</sup>]] if partial functions are allowed [[zooref#pps14|[PPS14]]].<br />
<br />
Contained in [[Complexity Zoo:U#upostbppcc|UPostBPP<sup>cc</sup>]].<br />
<br />
----<br />
<br />
===== <span id="pparnp" style="color:red">P<sup>||NP</sup></span>: [[#p|P]] With Parallel Queries To [[Complexity Zoo:N#np|NP]] =====<br />
Equals [[#pnplog|P<sup>NP[log]</sup>]] ([[zooref#bh91|[BH91]]] and [[zooref#hem89|[Hem89]]] independently).<br />
<br />
----<br />
===== <span id="pnpk" style="color:red">P<sup>NP[k]</sup></span>: [[#p|P]] With k [[Complexity Zoo:N#np|NP]] Queries(for constant k) =====<br />
Equals [[#p|P]] with 2<sup>k</sup>-1 parallel queries to [[Complexity Zoo:N#np|NP]] (i.e. queries that do not depend on the outcomes of previous queries) ([[zooref#bh91|[BH91]]] and [[zooref#hem89|[Hem89]]] independently).<br />
<br />
If P<sup>NP[1]</sup> = P<sup>NP[2]</sup>, then P<sup>NP[1]</sup> = [[#pnplog|P<sup>NP[log]</sup>]] and indeed [[#ph|PH]] collapses to &Delta;<sub>3</sub>P (attributed in [[zooref#har87b|[Har87b]]] to J. Kadin).<br />
<br />
----<br />
===== <span id="pnplog" style="color:red">P<sup>NP[log]</sup></span>: [[#p|P]] With Log [[Complexity Zoo:N#np|NP]] Queries =====<br />
Also known as [[Complexity Zoo:T#theta2p|Θ<sub>2</sub><sup>P</sup>]].<br />
<br />
The class of decision problems solvable by a [[#p|P]] machine, that can make O(log n) queries to an [[Complexity Zoo:N#np|NP]] oracle (where n is the length of the input).<br />
<br />
Equals [[#pparnp|P<sup>&#124;&#124;NP</sup>]], the class of decision problems solvable by a [[#p|P]] machine that can make polynomially many <i>nonadaptive</i> queries to an [[Complexity Zoo:N#np|NP]] oracle (i.e. queries that do not depend on the outcomes of previous queries) ([[zooref#bh91|[BH91]]] and [[zooref#hem89|[Hem89]]] independently).<br />
<br />
P<sup>NP[log]</sup> is contained in [[#pp|PP]] [[zooref#bhw89|[BHW89]]].<br />
<br />
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<sup>NP[log]</sup> [[zooref#hhr97|[HHR97]]].<br />
<br />
Contains [[#pnpk|P<sup>NP[k]</sup>]] for all constants k.<br />
<br />
----<br />
<br />
===== <span id="pnplog2" style="color:red">P<sup>NP[log^2]</sup></span>: [[#p|P]] With Log<sup>2</sup> [[Complexity Zoo:N#np|NP]] Queries =====<br />
Same as [[#pnplog|P<sup>NP[log]</sup>]], except that now log<sup>2</sup> queries can be made.<br />
<br />
The model-checking problem for a certain temporal logic is P<sup>NP[log^2]</sup>-complete [[zooref#sch03|[Sch03]]].<br />
<br />
For all k ≥ 1, [[#p|P]] with log<sup>k</sup> adaptive queries to [[Complexity Zoo:N#np|NP]] coincides with [[#p|P]] with log<sup>k−1</sup> rounds of (polynomially many) nonadaptive queries [[zooref#cs92|[CS92]]].<br />
<br />
----<br />
<br />
===== <span id="pobdd" style="color:red">P-OBDD</span>: Polynomial-Size Ordered Binary Decision Diagram =====<br />
An <i>ordered binary decision diagram (OBDD)</i> is a branching program (see [[#kpbp|k-PBP]]), with the additional constraint that if x<sub>i</sub> is queried before x<sub>j</sub> on any path, then i&lt;j.<br />
<br />
Then P-OBDD is the class of decision problems solvable by polynomial-size OBDD's.<br />
<br />
Contained in [[#pbp|PBP]], as well as [[Complexity Zoo:B#bppobdd|BPP-OBDD]].<br />
<br />
----<br />
===== <span id="podn" style="color:red">PODN</span>: Polynomial Odd Degree Node =====<br />
The subclass of [[Complexity Zoo:T#tfnp|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."<br />
<br />
Equals [[#ppa|PPA]] [[zooref#pap90|[Pap90]]].<br />
<br />
----<br />
===== <span id="polyl" style="color:red">polyL</span>: Polylogarithmic Space =====<br />
Equals [[Complexity Zoo:D#dspace|DSPACE]]((log n)<sup>c</sup>).<br />
<br />
In contrast to [[Complexity Zoo:L#l|L]], which is contained in [[#p|P]], it is not known if polyL is contained in [[#p|P]] or vice versa. On the other hand, we do know that polyL does not equal [[#p|P]], since (for example) polyL does not have complete problems under many-to-one logspace reductions.<br />
<br />
----<br />
===== <span id="postbpp" style="color:red">PostBPP</span>: [[Complexity Zoo:B#bpp|BPP]] With Postselection =====<br />
Alias for [[Complexity Zoo:B#bpppath|BPP<sub>path</sub>]].<br />
<br />
----<br />
===== <span id="postbppcc" style="color:red">PostBPP<sup>cc</sup></span>: Communication Complexity [[Complexity Zoo:P#postbpp|PostBPP]] =====<br />
<br />
The corresponding model consists of randomized protocols that may output 0, 1, or "abort", such that on every input, the non-abort probability is at least some &alpha;>0 (which is to be thought of as a function of n), and conditioned on not aborting, the output is correct with probability at least 2/3. The cost of a protocol is defined to be its communication cost plus log(1/&alpha;).<br />
<br />
Contained in, but does not equal, [[Complexity Zoo:P#ppcc|PP<sup>cc</sup>]] [[zooref#kla03|[Kla03]]].<br />
<br />
Contained in [[Complexity Zoo:P#phcc|PH<sup>cc</sup>]].<br />
<br />
The complexity measure corresponding to PostBPP<sup>cc</sup> is equivalent to the "extended discrepancy bound" [[zooref#gl14|[GL14]]].<br />
<br />
----<br />
<br />
===== <span id="postbqp" style="color:red">PostBQP</span>: [[Complexity Zoo:B#bqp|BQP]] With Postselection =====<br />
A class inspired by the proverb, "if at first you don't succeed, try, try again."<br />
<br />
Formally, the class of decision problems solvable by a [[Complexity Zoo:B#bqp|BQP]] machine such that<br />
<ul><br />
<li>If the answer is 'yes' then the second qubit has at least 2/3 probability of being measured 1, <i>conditioned</i> on the first qubit having been measured 1.</li><br />
<li>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.</li><br />
<li>On any input, the first qubit has a nonzero probability of being measured 1.</li><br />
</ul><br />
Defined in [[zooref#aar05b|[Aar05b]]], where it is also shown that PostBQP equals [[#pp|PP]].<br />
<br />
[[zooref#aar05b|[Aar05b]]] also gives the following alternate characterizations of PostBQP (and therefore of [[#pp|PP]]):<br />
<ul><br />
<li>The quantum analogue of [[Complexity Zoo:B#bpppath|BPP<sub>path</sub>]].</li><br />
<li>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.</li><br />
<li>The class of problems solvable in quantum polynomial time if we take the probability of measuring a basis state with amplitude &alpha; to be not |&alpha;|<sup>2</sup> but |&alpha;|<sup>p</sup>, 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.)</li><br />
</ul><br />
<br />
----<br />
<br />
===== <span id="pp" style="color:red">PP</span>: Probabilistic Polynomial-Time =====<br />
The class of decision problems solvable by an [[Complexity Zoo:N#np|NP]] machine such that<br />
<ol><br />
<li>If the answer is 'yes' then at least 1/2 of computation paths accept.</li><br />
<li>If the answer is 'no' then less than 1/2 of computation paths accept.</li><br />
</ol><br />
Defined in [[zooref#gil77|[Gil77]]].<br />
<br />
PP is closed under union and intersection [[zooref#brs91|[BRS91]]] (this was an open problem for 14 years).<br />
<br />
Contains [[#pnplog|P<sup>NP[log]</sup>]] [[zooref#bhw89|[BHW89]]].<br />
<br />
Equals PP<sup>[[Complexity Zoo:B#bpp|BPP]]</sup> [[zooref#kst89b|[KST+89b]]] as well as [[#postbqp|PostBQP]] [[zooref#aar05b|[Aar05b]]].<br />
<br />
However, there exists an oracle relative to which PP does not contain [[Complexity Zoo:D#delta2p|&#916;<sub>2</sub>P]] [[zooref#bei94|[Bei94]]].<br />
<br />
[[#ph|PH]] is in [[#ppp2|P<sup>PP</sup>]] [[zooref#tod89|[Tod89]]].<br />
<br />
[[Complexity Zoo:B#bqp|BQP]] is low for PP; i.e. PP<sup>BQP</sup> = PP [[zooref#fr98|[FR98]]].<br />
<br />
For a random oracle A, PP<sup>A</sup> is strictly contained in [[#pspace|PSPACE]]<sup>A</sup> with probability 1 [[zooref#abf94|[ABF+94]]].<br />
<br />
For any fixed k, there exists a language in PP that does not have circuits of size n<sup>k</sup> [[zooref#vin04b|[Vin04b]]]. Indeed, there exists a language in PP that does not even have quantum circuits of size n<sup>k</sup> with quantum advice [[zooref#aar06|[Aar06]]].<br />
<br />
By contrast, there exists an oracle relative to which PP has linear-size circuits [[zooref#aar06|[Aar06]]].<br />
<br />
PP can be generalized to the counting hierarchy [[Complexity Zoo:C#ch|CH]].<br />
<br />
----<br />
<br />
===== <span id="ppcc" style="color:red">PP<sup>cc</sup></span>: Communication Complexity [[#pp|PP]] =====<br />
Defined in [[zooref#bfs86|[BFS86]]], '''PP<sup>cc</sup>''' is one of two ways to define a communication complexity analogue of [[#pp|PP]]. In PP<sup>cc</sup>, we note that in an algorithm that uses an amount of random bits bounded by <math>c</math>, the bias between the accept and reject probabilities can be no smaller than <math>2^c</math>. Thus, in PP<sup>cc</sup>, the communication complexity is defined as the sum of the traditional communication complexity (the number of exchanged bits) and the log of the reciprocal of the worst-case (smallest) bias.<br />
<br />
The difference between this class and [[Complexity Zoo:U#uppcc|UPP<sup>cc</sup>]] is discussed further in [[zooref#bvw07|[BVW07]]], where it is shown that PP<sup>cc</sup> &sub; UPP<sup>cc</sup>.<br />
<br />
The complexity measure corresponding to PP<sup>cc</sup> is equivalent to the "discrepancy bound" [[zooref#kla07|[Kla07]]].<br />
<br />
''See also:'' [[Complexity Zoo:U#uppcc|UPP<sup>cc</sup>]].<br />
----<br />
<br />
===== <span id="pppoly" style="color:red">PP/poly</span>: Nonuniform [[#pp|PP]] =====<br />
Contains [[Complexity Zoo:B#bqpqpoly|BQP/qpoly]] [[zooref#aar04b|[Aar04b]]].<br />
<br />
If PP/poly = [[#ppoly|P/poly]] then [[#pp|PP]] is contained in [[#ppoly|P/poly]]. Indeed this is true with any syntactically defined class in place of [[#pp|PP]]. An implication is that any unrelativized separation of [[Complexity Zoo:B#bqpqpoly|BQP/qpoly]] from [[Complexity Zoo:B#bqpmpoly|BQP/mpoly]] would imply that [[#pp|PP]] does not have polynomial-size circuits.<br />
<br />
----<br />
===== <span id="ppa" style="color:red">PPA</span>: Polynomial Parity Argument =====<br />
Defined in [[zooref#pap94b|[Pap94b]]]; see also [[zooref#bce95|[BCE+95]]].<br />
<br />
The subclass of [[Complexity Zoo:T#tfnp|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."<br />
<br />
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.<br />
<br />
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 [[zooref#pap94|[Pap94]]]). So this problem is in PPA.<br />
<br />
Another problem in PPA is finding an Arrow-Debreu equilibrium, given the goods and utility functions of traders in a marketplace.<br />
<br />
Jeřábek [[zooref#jer12|[Jeř12]]] showed that computing the square root mod n and finding quadratic nonresidues mod n are both in PPA. Further, [[Complexity Garden#integer factorization|integer factorization]] is in PPA under the assumption of a generalized Riemann hypothesis.<br />
<br />
A complete problem for PPA is Sperner's lemma for non-orientable 3-manifolds. [[zooref#gri01|[Gri01]]]<br />
<br />
Contained in [[Complexity Zoo:T#tfnp|TFNP]].<br />
<br />
Contains [[#ppad|PPAD]].<br />
<br />
There exist oracles relative to which PPA does not contain [[#pls|PLS]] [[zooref#bm04|[BM04]]] and [[#ppp|PPP]] [[zooref#bce95|[BCE+95]]]. There also exists an oracle relative to which PPA is not contained in [[#ppp|PPP]] [[zooref#bce95|[BCE+95]]].<br />
<br />
----<br />
<br />
===== <span id="ppad" style="color:red">PPAD</span>: Polynomial Parity Argument (Directed) =====<br />
Defined in [[zooref#pap94b|[Pap94b]]]; see also [[zooref#bce95|[BCE+95]]].<br />
<br />
Same as [[#ppa|PPA]], except now the graph is directed, and we're asked to find either a source or a sink.<br />
<br />
Contained in [[#ppa|PPA]] and [[#ppads|PPADS]].<br />
<br />
NASH, the problem of finding a Nash equilibrium in a normal form game of two or more players with specified utilities, is in PPAD [[zooref#pap94b|[Pap94b]]], and proved to be complete for PPAD with four players in [[zooref#dgp05|[DGP05]]], and shortly after extended to the case of three players [[zooref#dp05|[DP05]]] and independently [[zooref#cd05|[CD05]]].<br />
<br />
There exists an oracle relative to which [[#ppp|PPP]] is not contained in PPAD [[zooref#bce95|[BCE+95]]].<br />
There exists an oracle relative to which PPAD is not contained in [[Complexity Zoo:B#bqp|BQP]] [[zooref#li11|[Li11]]].<br />
<br />
----<br />
<br />
===== <span id="ppads" style="color:red">PPADS</span>: Polynomial Parity Argument (Directed, Sink) =====<br />
Defined in [[zooref#pap94b|[Pap94b]]]; see also [[zooref#bce95|[BCE+95]]].<br />
<br />
Same as [[#ppa|PPA]], except now the graph is directed, and we're asked to find a sink.<br />
<br />
Contained in [[#ppp|PPP]].<br />
<br />
Contains [[#ppad|PPAD]].<br />
<br />
----<br />
===== <span id="ppp" style="color:red">PPP</span>: Polynomial Pigeonhole Principle =====<br />
Defined in [[zooref#pap94b|[Pap94b]]]; see also [[zooref#bce95|[BCE+95]]].<br />
<br />
The subclass of [[Complexity Zoo:T#tfnp|TFNP]] function problems that are guaranteed to have a solution because of the Pigeonhole Principle.<br />
<br />
More precisely, we're given a Boolean circuit, that maps n-bit strings to n-bit strings. The problem is to return <i>either</i> an input that maps to 0<sup>n</sup>, <i>or</i> two inputs that map to the same output.<br />
<br />
Contained in [[Complexity Zoo:T#tfnp|TFNP]].<br />
<br />
Contains [[#ppads|PPADS]].<br />
<br />
[[zooref#bce95|[BCE+95]]] give oracles relative to which PPP is not contained in [[#ppa|PPA]] and [[#ppad|PPAD]], and [[#ppa|PPA]] is not contained in PPP.<br />
<br />
[[zooref#mor01|[Mor01]]] gives an oracle relative to which PPP is not contained in [[#pls|PLS]].<br />
<br />
Whether [[#pls|PLS]] is not contained in PPP relative to some oracle remains open.<br />
<br />
----<br />
===== <span id="ppp2" style="color:red">P<sup>PP</sup></span>: [[#p|P]] With [[#pp|PP]] Oracle =====<br />
A level of the counting hierarchy [[Complexity Zoo:C#ch|CH]].<br />
<br />
It is not known whether there exists an oracle relative to which P<sup>PP</sup> does not equal [[#pspace|PSPACE]].<br />
<br />
Contains [[#pp|PP]]<sup>[[#ph|PH]]</sup> [[zooref#tod89|[Tod89]]].<br />
<br />
Equals [[#psharpp|P<sup>#P</sup>]] (exercise for the visitor).<br />
<br />
Since the permanent of a matrix is [[Complexity Zoo:Symbols#sharpp|#P]]-complete [[zooref#val79|[Val79]]], Toda's theorem implies that any problem in the polynomial hierarchy can be solved by computing a sequence of permanents.<br />
<br />
----<br />
<br />
===== <span id="pqmalog" style="color:red">P<sup>QMA[log]</sup></span>: [[#p|P]] With Log [[Complexity Zoo:Q#qma|QMA]] Queries =====<br />
The class of decision problems solvable by a [[#p|P]] machine, that can make O(log n) queries to a [[Complexity Zoo:Q#qma|QMA]] oracle (where n is the length of the input). <br />
<br />
Defined in [[zooref#amb14|[Amb14]]].<br />
<br />
Equals [[#pparqma|P<sup>||QMA</sup>]] [[zooref#gpy19|[GPY19]]].<br />
<br />
Estimating local observables [[zooref#amb14|[Amb14]]], [[zooref#gy16|[GY16]]] and local correlation functions [[zooref#gy16|[GY16]]] against ground states of local Hamiltonians is P<sup>QMA[log]</sup>-complete.<br />
<br />
Estimating local observables remains P<sup>QMA[log]</sup>-complete even on 2D physical systems and on the 1D line [[zooref#gpy19|[GPY19]]].<br />
<br />
P<sup>QMA[log]</sup> is contained in [[#pp|PP]] [[zooref#gy16|[GY16]]].<br />
<br />
----<br />
<br />
===== <span id="pparqma" style="color:red">P<sup>||QMA</sup></span>: [[#p|P]] With Parallel Queries To [[Complexity Zoo:Q#qma|QMA]] =====<br />
The class of decision problems solvable by a [[#p|P]] machine that can make a polynomial number of non-adaptive queries to a [[Complexity Zoo:Q#qma|QMA]] oracle.<br />
<br />
Equals [[#pqmalog|P<sup>QMA[log]</sup>]] [[zooref#gpy19|[GPY19]]].<br />
<br />
----<br />
<br />
===== <span id="pquery" style="color:red">PQUERY</span>: PSPACE With Polynomial Queries =====<br />
The class of decision problems solvable in polynomial space using at most a polynomial number of queries to the oracle.<br />
<br />
Thus, PQUERY = [[#pspace|PSPACE]], but PQUERY<sup>A</sup> does not equal [[#pspace|PSPACE]]<sup>A</sup> for some oracles A.<br />
<br />
Defined in [[zooref#kur83|[Kur83]]], where it was actually put forward as a serious argument (!!) against believing relativization results.<br />
<!-- TODO: What does the (!!) above mean? --><br />
<br />
----<br />
<br />
===== <span id="ppspace" style="color:red">PPSPACE</span>: Probabilistic [[#pspace|PSPACE]] =====<br />
Same as [[Complexity Zoo:I#ipp|IPP]], except that [[Complexity Zoo:I#ipp|IPP]] uses private coins while PPSPACE uses public coins.<br />
<br />
Can also be defined as a probabilistic version of [[#pspace|PSPACE]].<br />
<br />
Equals [[#pspace|PSPACE]].<br />
<br />
Defined in [[zooref#pap83|[Pap83]]].<br />
<br />
----<br />
===== <span id="pr" style="color:red">PR</span>: Primitive Recursive Functions =====<br />
Basically, the class of functions definable by recursively building up arithmetic functions: addition, multiplication, exponentiation, tetration, etc. What's <i>not</i> 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 [[Complexity Zoo:R#r|R]].<br />
<br />
Alternatively, the PR functions are exactly those functions that can be computed via programs in any reasonable, idealized ALGOL-like programming language where only <i>definite</i> loops are allowed, that is, loops where the number of iterations is specified before the loop starts (so FOR-loops are okay but not WHILE- or REPEAT-loops), and recursive calls are not allowed. <br />
<br />
Alternatively, the PR functions are those functions whose termination can be proved by well-founded induction using an ordinal less than ω<sup>ω</sup>. (There are other systems for higher ordinals. Notably, Gödel's System T is an extension of PR with higher-order functions, and it allows all functions whose termination can be proved by well-founded induction using an ordinal less than ε<sub>0</sub>, including Ackermann's function.)<br />
<br />
An interesting difference is that PR functions can be explicitly enumerated, whereas functions in [[Complexity Zoo:R#r|R]] cannot be (since otherwise the halting problem would be decidable). In this sense, PR is a "syntactic" class whereas [[Complexity Zoo:R#r|R]] is "semantic."<br />
<br />
On the other hand, we can "enumerate" any [[Complexity Zoo:R#re|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.<br />
<br />
PR strictly contains [[Complexity Zoo:E#elementary|ELEMENTARY]].<br />
<br />
----<br />
<br />
===== <span id="pr2" style="color:red">P<sub>R</sub></span>: Polynomial-Time Over The Reals =====<br />
An analog of [[#p|P]] for Turing machines over a real number field.<br />
<br />
Defined in [[zooref#bcs97|[BCS+97]]].<br />
<br />
See also [[#pc|P<sub>C</sub>]], [[Complexity Zoo:N#npc2|NP<sub>C</sub>]], [[Complexity Zoo:N#npr|NP<sub>R</sub>]], [[Complexity Zoo:V#vp|VP<sub>k</sub>]].<br />
<br />
----<br />
===== <span id="prhspace" style="color:red">Pr<sub>H</sub>SPACE(f(n))</span>: Unbounded-Error Halting Probabilistic f(n)-Space =====<br />
Has the same relation to [[Complexity Zoo:D#dspace|DSPACE]](f(n)) as [[#pp|PP]] does to [[#p|P]]. The Turing machine has to halt on every input <i>and</i> every setting of the random tape.<br />
<br />
Equals [[#prspace|PrSPACE]](f(n)) [[zooref#jun85|[Jun85]]].<br />
<br />
----<br />
===== <span id="promisebpp" style="color:red">PromiseBPP</span>: Promise-Problem [[Complexity Zoo:B#bpp|BPP]] =====<br />
Same as [[#promiserp|PromiseRP]], but for [[Complexity Zoo:B#bpp|BPP]] instead of [[Complexity Zoo:R#rp|RP]].<br />
<br />
Defined in [[zooref#bf99|[BF99]]].<br />
<br />
----<br />
===== <span id="promisebqp" style="color:red">PromiseBQP</span>: Promise-Problem [[Complexity Zoo:B#bqp|BQP]] =====<br />
Same as [[#promisebpp|PromiseBPP]], but for [[Complexity Zoo:B#bqp|BQP]] instead of [[Complexity Zoo:B#bpp|BPP]].<br />
<br />
If PromiseBQP = [[#promisep|PromiseP]] then [[Complexity Zoo:B#bqpmpoly|BQP/mpoly]] = [[#ppoly|P/poly]].<br />
<br />
----<br />
<br />
===== <span id="promisep" style="color:red">PromiseP</span>: Promise-Problem [[#p|P]] =====<br />
The class of promise problems solvable by a [[#p|P]] machine.<br />
<br />
----<br />
===== <span id="promiserp" style="color:red">PromiseRP</span>: Promise-Problem [[Complexity Zoo:R#rp|RP]] =====<br />
The class of promise problems solvable by an [[Complexity Zoo:R#rp|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.<br />
<br />
Defined in [[zooref#bf99|[BF99]]], where it was also shown that [[Complexity Zoo:B#bpp|BPP]] is in [[Complexity Zoo:R#rp|RP]]<sup>PromiseRP[1]</sup> (i.e. with a single oracle query to PromiseRP).<br />
<br />
Contained in [[#promisebpp|PromiseBPP]].<br />
<br />
----<br />
<br />
===== <span id="promiseup" style="color:red">PromiseUP</span>: Promise-Problem [[Complexity Zoo:U#up|UP]] =====<br />
The class of promise problems solvable by an [[Complexity Zoo:U#up|UP]] machine. I.e., the nondeterministic machine must have a unique accepting path for "yes" inputs, and no accepting paths "no" inputs, but could have any number of accepting paths for inputs that do not satisfy the promise.<br />
<br />
Although not originally stated with this notation, the main result of [[zooref#vv86|[VV86]]] is that [[Complexity Zoo:N#np|NP]] is contained in [[ComplexityZoo:R#rp|RP]]<sup>PromiseUP</sup>.<br />
<br />
----<br />
<br />
===== <span id="prspace" style="color:red">PrSPACE(f(n))</span>: Unbounded-Error Probabilistic f(n)-Space =====<br />
Has the same relation to [[Complexity Zoo:D#dspace|DSPACE]](f(n)) as [[#pp|PP]] does to [[#p|P]]. The Turing machine has to halt with probability 1 on every input.<br />
<br />
Contained in [[Complexity Zoo:D#dspace|DSPACE]](f(n)<sup>2</sup>) [[zooref#bcp83|[BCP83]]].<br />
<br />
Equals [[#prhspace|Pr<sub>H</sub>SPACE]](f(n)) [[zooref#jun85|[Jun85]]].<br />
<br />
----<br />
===== <span id="psel" style="color:red">P-Sel</span>: P-Selective Sets =====<br />
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.<br />
<br />
Defined in [[zooref#sel79|[Sel79]]], where it was also shown that if [[Complexity Zoo:N#np|NP]] is contained in P-Sel then [[#p|P]] = [[Complexity Zoo:N#np|NP]].<br />
<br />
There exist P-selective sets that are not recursive (i.e. not in [[Complexity Zoo:R#r|R]]).<br />
<br />
----<br />
===== <span id="psk" style="color:red">PSK</span>: Polynomial Sink =====<br />
Yeah, I'm told that's what the S and K stand for. Go figure.<br />
<br />
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.<br />
<br />
Defined in [[zooref#pap90|[Pap90]]].<br />
<br />
Equals [[#ppads|PPADS]].<br />
<br />
----<br />
===== <span id="pspace" style="color:red">PSPACE</span>: Polynomial-Space =====<br />
The class of decision problems solvable by a Turing machine in polynomial space.<br />
<br />
Equals [[Complexity Zoo:N#npspace|NPSPACE]] [[zooref#sav70|[Sav70]]], [[Complexity Zoo:A#ap|AP]] [[zooref#cks81|[CKS81]]], and [[Complexity Zoo:C#czk|CZK]] assuming the existence of one-way functions [[zooref#bgg90|[BGG+90]]].<br />
<br />
Equals [[Complexity Zoo:I#ip|IP]] [[zooref#sha90|[Sha90]]], but PSPACE strictly contains [[#ip|IP]] with probability 1 [[zooref#ccg94|[CCG+94]]].<br />
<br />
Contains [[#p|P<sup>#P</sup>]] ([[#p|P]] with a [[Complexity Zoo:Symbols#sharpp|#P]] oracle).<br />
<br />
A canonical PSPACE-complete problem is [[Complexity_Garden#qbf|QBF]].<br />
<br />
Relative to a random oracle, PSPACE strictly contains [[#ph|PH]] with probability 1 [[zooref#cai86|[Cai86]]].<br />
<br />
PSPACE has a complete problem that is both downward self-reducible and random self-reducible [[zooref#tv02|[TV02]]]. It is the largest class with such a complete problem.<br />
<br />
Contained in [[Complexity Zoo:E#exp|EXP]]. There exists an oracle relative to which this containment is proper [[zooref#dek76|[Dek76]]].<br />
<br />
In descriptive complexity, PSPACE can be defined with 4 differents kind of formulae, [[#Complexity_Zoo:F#fot|FO(<math>2^{n^{O(1)}}</math>)]] which is also [[#Complexity_Zoo:F#fopfp|FO(PFP)]] and [[#Complexity_Zoo:S#fot|SO(<math>n^{O(1)}</math>)]] which is also [[#Complexity_Zoo:F#sotc|SO(TC)]].<br />
----<br />
<br />
===== <span id="pspacecc" style="color:red">PSPACE<sup>cc</sup></span>: Communication Complexity [[#pspace|PSPACE]] =====<br />
<br />
This class is not defined in terms of space, but rather by analogy with the characterization [[Complexity Zoo:P#pspace|PSPACE]]=[[Complexity Zoo:A#ap|AP]]. Specifically, a protocol corresponds to a boolean formula where each leaf represents (the indicator function of) a rectangle; the cost of a protocol is the log of the size of the formula.<br />
<br />
Contains [[Complexity Zoo:P#phcc|PH<sup>cc</sup>]].<br />
<br />
----<br />
<br />
===== <span id="pspacepoly" style="color:red">PSPACE/poly</span>: [[#pspace|PSPACE]] With Polynomial-Size Advice =====<br />
Contains [[Complexity Zoo:Q#qmaqpoly|QMA/qpoly]] [[zooref#aar06b|[Aar06b]]].<br />
<br />
----<br />
<br />
===== <span id="pt1" style="color:red">PT<sub>1</sub></span>: Polynomial Threshold Functions =====<br />
The class of Boolean functions f:{-1,1}<sup>n</sup>->{-1,1} such that f(x)=sgn(p(x)), where p is a polynomial having a number of terms polynomial in n.<br />
<br />
Defined in [[zooref#bs90|[BS90]]], where it was also shown that PT<sub>1</sub> contains [[#pl1|PL<sub>1</sub>]] (and this inclusion is strict), and that PT<sub>1</sub> is contained in [[#plinfinity|PL<sub>&#8734;</sub>]] (and this inclusion is strict).<br />
<br />
----<br />
<br />
===== <span id="ptape" style="color:red">PTAPE</span>: Archaic for [[#pspace|PSPACE]] =====<br />
<br />
----<br />
===== <span id="ptas" style="color:red">PTAS</span>: Polynomial-Time Approximation Scheme =====<br />
The subclass of [[Complexity Zoo:N#npo|NPO]] problems that admit an <i>approximation scheme</i> in the following sense. For any &#949;&gt;0, there is a polynomial-time algorithm that is guaranteed to find a solution whose cost is within a 1+&#949; factor of the optimum cost. (However, the exponent of the polynomial might depend strongly on &#949;.)<br />
<br />
Contains [[Complexity Zoo:F#fptas|FPTAS]], and is contained in [[Complexity Zoo:A#apx|APX]].<br />
<br />
As an example, the Traveling Salesman Problem in the Euclidean plane is in PTAS [[zooref#aro96|[Aro96]]].<br />
<br />
Defined in [[zooref#acg99|[ACG+99]]].<br />
<br />
----<br />
===== <span id="ptwk" style="color:red">PT/WK(f(n),g(n))</span>: Parallel Time f(n) / Work g(n) =====<br />
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).<br />
<br />
The union of PT/WK(log<sup>k</sup>n, n<sup>k</sup>) over all constants k equals [[Complexity Zoo:N#nc|NC]].<br />
<br />
----<br />
===== <span id="pzk" style="color:red">PZK</span>: Perfect Zero Knowledge =====<br />
Same as [[Complexity Zoo:S#szk|SZK]], but now the two distributions must be <i>identical</i>, not merely statistically close. (The "two distributions" are (1) the distribution over the verifier's view of his interaction with the prover, conditioned on the verifier's random coins, and (2) the distribution over views that the verifier can <i>simulate</i> without the prover's help.)<br />
<br />
Contained in [[Complexity Zoo:S#szk|SZK]].<br />
<br />
See also: [[Complexity Zoo:C#czk|CZK]].</div>Atn