Complexity Zoo:P - Revision history

Svennik: Added the partially-blind one-counter languages

2026-05-04T13:39:32Z

Added the partially-blind one-counter languages

Lv02: /* PSPACE, IP: former statement was contradictory and not what the cited paper actually states */

2025-07-18T16:28:45Z

PSPACE, IP: former statement was contradictory and not what the cited paper actually states

Kmarw: add puresuperqma class

2025-01-14T06:02:00Z

add puresuperqma class

Mormegil: /* P: Polynomial-Time */ fix link

2024-12-18T11:54:17Z

P: Polynomial-Time: fix link

Yirkajk: /* PP: Probabilistic Polynomial-Time */ update ref for result PP does not have small quantum circuits

2024-07-07T15:53:35Z

PP: Probabilistic Polynomial-Time: update ref for result PP does not have small quantum circuits

Yirkajk: /* PP: Probabilistic Polynomial-Time / add lowness of YQP and APP.

2024-07-07T15:52:30Z

PP: Probabilistic Polynomial-Time: add lowness of YQP* and APP.

Yirkajk: /* PP: Probabilistic Polynomial-Time / add YQP is PP-low

2024-07-07T15:49:21Z

PP: Probabilistic Polynomial-Time: add YQP* is PP-low

Emil Jeřábek: /* PP: Probabilistic Polynomial-Time */

2024-05-29T08:43:46Z

PP: Probabilistic Polynomial-Time

Emil Jeřábek: /* P#P: P With #P Oracle */

2024-05-29T06:36:22Z

P#P: P With #P Oracle

Emil Jeřábek: /* P#P[1]: P With Single Query To #P Oracle */

2024-05-29T06:32:51Z

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

@@ Line 32: / Line 32: @@
 P can be computed by interactive protocols (see  [[Complexity Zoo:I#ip|IP]]) where the verifier runs in log space (see [[Complexity Zoo:L#l|L]] and [[Complexity Zoo:B#bpl|BPL]]) [[zooref#gkr15|[GKR15]]].
 ----
 ===== <span id="plog" style="color:red">P/log</span>: [[#p|P]] With Logarithmic Advice =====
 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.
@@ Line 138: / Line 137: @@
 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]]].
 ----
 ===== <span id="pbp" style="color:red">PBP</span>: Polynomial-Size Branching Program =====

@@ Line 831: / Line 831: @@
 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]]].
-Equals [[Complexity Zoo:I#ip|IP]] [[zooref#sha90|[Sha90]]], but PSPACE strictly contains [[#ip|IP]] with probability 1 [[zooref#ccg94|[CCG+94]]].
+Equals [[Complexity Zoo:I#ip|IP]] [[zooref#sha90|[Sha90]]], but for a random oracle A, PSPACE<sup>A</sup> strictly contains [[Complexity Zoo:I#ip|IP]]<sup>A</sup> with probability 1 [[zooref#ccg94|[CCG+94]]].
 Contains [[#psharpp|P<sup>#P</sup>]] ([[#p|P]] with a [[Complexity Zoo:Symbols#sharpp|#P]] oracle).

← Older revision		Revision as of 06:02, 14 January 2025
Line 883:		Line 883:

	The union of PT/WK(log<sup>k</sup>n, n<sup>k</sup>) over all constants k equals [[Complexity Zoo:N#nc\|NC]].		The union of PT/WK(log<sup>k</sup>n, n<sup>k</sup>) over all constants k equals [[Complexity Zoo:N#nc\|NC]].
		+
		+	----
		+	===== <span id="puresuperqma" style="color:red">PureSuperQMA</span>: A pure-state analog of [[Complexity Zoo:Q#qma-plus\|SuperQMA]] =====
		+
		+	Same as QMA, except now <b>the witness is a pure state</b>, and the verifier can directly obtain the probability that any one of a polynomial number of observables of the witness, if measured, would equal 1. (In the usual model, by contrast, one can only sample an observable.) Without the pure state restriction, this class is [[Complexity Zoo:Q#qma-plus\|SuperQMA]].
		+
		+	Defined in [[zooref#kr24\|[KR24]]] whose complete problem is the pure state marginal problem. It is known to be QMA-hard but contained in PSPACE and QMA(2). Surprisingly, it is unknown whether this class equals [[Complexity Zoo:Q#qma-plus\|SuperQMA]] = [[Complexity Zoo:Q#qma\|QMA]].

	----		----

@@ Line 26: / Line 26: @@
 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)]]
-P queries are exactly the one that can be written in the [[#Complexity_Zoo:S#while|While<sup>/cons</sup>]] languages.
+P queries are exactly the one that can be written in the [[Complexity_Zoo:W#while|While<sup>/cons</sup>]] languages.
 P is the class of decision problems solvable by a (logspace) ''uniform'' family of polynomial-size Boolean circuits.

@@ Line 582: / Line 582: @@
 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]]].
-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]]].
+For any fixed k, there exists a language in PP that does not have circuits of size n<sup>k</sup> [[zooref#vin04b|[Vin04b]]]. <br>
 By contrast, there exists an oracle relative to which PP has linear-size circuits [[zooref#aar06|[Aar06]]].

@@ Line 575: / Line 575: @@
 [[#ph|PH]] is in [[#ppp2|P<sup>PP</sup>]] [[zooref#tod89|[Tod89]]].
-[[Complexity Zoo:B#bpp|BPP]] [[zooref#kst89b|[KST+89b]]] and even [[Complexity Zoo:B#bqp|BQP]] [[zooref#fr98|[FR98]]] and [[Complexity Zoo:Y#yqp*|YQP*]] [[zooref#yir24|[Yir24]]] are low for PP: i.e., PP<sup>BQP</sup> = PP. Equals [[#postbqp|PostBQP]] [[zooref#aar05b|[Aar05b]]].
+[[Complexity Zoo:B#bpp|BPP]] [[zooref#kst89b|[KST+89b]]] and even [[Complexity Zoo:B#bqp|BQP]] [[zooref#fr98|[FR98]]] and [[Complexity Zoo:Y#yqp*|YQP*]] [[zooref#yir24|[Yir24]]] are low for PP: i.e., PP<sup>BQP</sup> = PP. <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]]].

@@ Line 569: / Line 569: @@
 Defined in [[zooref#gil77|[Gil77]]].
-PP is closed under union and intersection [[zooref#brs91|[BRS91]]] (this was an open problem for 14 years). More generally, P<sup>PP[log]</sup> = PP.
+PP is closed under union and intersection [[zooref#brs91|[BRS91]]] (this was an open problem for 14 years). More generally, P<sup>PP[log]</sup> = PP. Even more generally, PP is closed under polynomial-time truth-table reductions, or even ''k''-round reductions for any constant ''k'' [[zooref#fr96|[FR96]]].
 Contains [[#pnplog|P<sup>NP[log]</sup>]] [[zooref#bhw89|[BHW89]]] and [[Complexity Zoo:Q#qma|QMA]] (see [[zooref#mw05|[MW05]]]). However, there exists an oracle relative to which PP does not contain [[Complexity Zoo:D#delta2p|&#916;<sub>2</sub>P]] [[zooref#bei94|[Bei94]]].

@@ Line 74: / Line 74: @@
 I decided this class is so important that it deserves an entry of its own, apart from [[Complexity Zoo:Symbols#sharpp|#P]].
-Contains [[#ph|PH]] [[zooref#tod89|[Tod89]]], and is contained in [[#pspace|PSPACE]].
+Contains [[#ph|PH]] [[zooref#tod89|[Tod89]]], and is contained in [[Complexity Zoo:C#ch|CH]] and in [[#pspace|PSPACE]].
 Equals [[#ppp2|P<sup>PP</sup>]] (exercise for the visitor).
 ----
 ===== <span id="psharpp1" style="color:red">P<sup>#P[1]</sup></span>: [[#p|P]] With Single Query To [[Complexity Zoo:Symbols#sharpp|#P]] Oracle =====
 Contains [[#ph|PH]] [[zooref#tod89|[Tod89]]]. Indeed, contains [[Complexity Zoo:M#mp2|MP]], which in turn contains [[Complexity Zoo:M#modph|ModPH]] [[zooref#gkr95|[GKR+95]]].