Complexity Zoo:O - Revision history

Svennik: Added One-Counter Languages

2026-05-04T13:28:53Z

Added One-Counter Languages

Hirsch: /* O2P: Second Level of the Oblivious Symmetric Hierarchy */

2024-05-09T20:06:56Z

O2P: Second Level of the Oblivious Symmetric Hierarchy

Emil Jeřábek: /* O2P: Second Level of the Oblivious Symmetric Hierarchy */

2024-05-03T12:19:53Z

O2P: Second Level of the Oblivious Symmetric Hierarchy

Quackack: /* O2P: Second Level of the Oblivious Symmetric Hierarchy */

2023-12-08T22:44:01Z

O2P: Second Level of the Oblivious Symmetric Hierarchy

Quackack at 20:38, 8 December 2023

2023-12-08T20:38:43Z

Quackack: /* O2P: Second Level of the Oblivious Symmetric Hierarchy */

2023-12-08T20:30:07Z

O2P: Second Level of the Oblivious Symmetric Hierarchy

Pys: /* OptP: Optimum Polynomial-Time */

2023-03-25T21:12:28Z

OptP: Optimum Polynomial-Time

Quackack: /* OMA: Oblivious MA */

2022-08-23T23:27:25Z

OMA: Oblivious MA

Emil Jeřábek: /* O2P: Second Level of the Oblivious Symmetric Hierarchy */ mention inclusion in P/poly

2021-07-06T18:54:15Z

O2P: Second Level of the Oblivious Symmetric Hierarchy: mention inclusion in P/poly

Quackack: /* O2P: Second Level of the Oblivious Symmetric Hierarchy */

2021-05-27T22:03:18Z

O2P: Second Level of the Oblivious Symmetric Hierarchy

← Older revision		Revision as of 13:28, 4 May 2026
Line 1:		Line 1:
	{{CZ-Letter-Menu\|O}}		{{CZ-Letter-Menu\|O}}
		+
		+	===== <span id="o2p" style="color:red">OCL</span>: One-Counter Languages =====
		+
		+	The class of languages accepted by nondeterministic one-counter automata:
		+	finite automata equipped with one nonnegative counter that can be incremented,
		+	decremented, and tested for zero. Equivalently, OCL is the class accepted by
		+	pushdown automata with a singleton stack alphabet, plus a bottom marker.
		+
		+	REG ⊊ OCL ⊊ CFL. As decision problems over strings, OCL ⊆ NL.
		+
		+	Examples include {a^n b^n : n ≥ 0} and the one-parenthesis Dyck language.
		+	The two-parenthesis Dyck language is CFL but not OCL.
		+
		+	Contains [[Complexity Zoo:D#DOCL\|DOCL]] and [[Complexity Zoo:P#PB-OCL\|PB-OCL]]. Contained in [[Complexity Zoo:C#CFL\|CFL]] and [[Complexity Zoo:N#NL\|NL]].
		+
		+	----

	===== <span id="oip" style="color:red">OIP</span>: Oblivious IP =====		===== <span id="oip" style="color:red">OIP</span>: Oblivious IP =====

← Older revision		Revision as of 20:06, 9 May 2024
Line 80:		Line 80:
	Contains [[Complexity Zoo:O#onp\|ONP]] and coONP [[zooref#gm15\|[GM15]]].		Contains [[Complexity Zoo:O#onp\|ONP]] and coONP [[zooref#gm15\|[GM15]]].

−	It follows from results of [[zooref#li23\|[Li23]]] that for each ''k'', O<sub>2</sub>P contains a language that has circuit complexity at least ''n<sup>k</sup>''. (Previously, this was known for NP ∪ O<sub>2</sub>P based on [[zooref#cr06\|[CR06]]].)	+	It follows [[zooref#glv24\|[GLV24]]] from results of [[zooref#li23\|[Li23]]] that for each ''k'', O<sub>2</sub>P contains a language that has circuit complexity at least ''n<sup>k</sup>''. (Previously, this was known for NP ∪ O<sub>2</sub>P based on [[zooref#cr06\|[CR06]]].)

@@ Line 72: / Line 72: @@
 <li>If the answer is 'no,' then for all y, P(x,y,z*) is false.</li>
 </ol>
-Note that this differs from [[#s2p|S<sub>2</sub>P]] in that the witnesses in each case must only depend on the length of the input, and not on the input itself. In particular, since the conditions imply that the answer is 'yes' iff P(x,y*,z*), the class O<sub>2</sub>P is included in [[Complexity Zoo:P#ppoly|P/poly]].
+Note that this differs from [[Complexity Zoo:S#s2p|S<sub>2</sub>P]] in that the witnesses in each case must only depend on the length of the input, and not on the input itself. In particular, since the conditions imply that the answer is 'yes' iff P(x,y*,z*), the class O<sub>2</sub>P is included in [[Complexity Zoo:P#ppoly|P/poly]].
 Less formally, O<sub>2</sub>P is the class of one-round games in which a prover and a disprover submit simultaneous moves to a deterministic, polynomial-time referee, and furthermore, there is a single winning move the prover can make that works for all x of length n that are yes-instances, and there is a single winning move the disprover can make that works for all x of length n that are no-instances.
@@ Line 80: / Line 80: @@
 Contains [[Complexity Zoo:O#onp|ONP]] and coONP [[zooref#gm15|[GM15]]].
-Contrast with [[Complexity Zoo:S#s2p|S<sub>2</sub>P]].
+It follows from results of [[zooref#li23|[Li23]]] that for each ''k'', O<sub>2</sub>P contains a language that has circuit complexity at least ''n<sup>k</sup>''. (Previously, this was known for NP ∪ O<sub>2</sub>P based on [[zooref#cr06|[CR06]]].)

← Older revision		Revision as of 22:44, 8 December 2023
Line 79:		Line 79:

	Contains [[Complexity Zoo:O#onp\|ONP]] and coONP [[zooref#gm15\|[GM15]]].		Contains [[Complexity Zoo:O#onp\|ONP]] and coONP [[zooref#gm15\|[GM15]]].
−
−	~~Does not have any fixed polynomial sized circuits [[zooref#li23\|[Li23]]].~~

	Contrast with [[Complexity Zoo:S#s2p\|S<sub>2</sub>P]].		Contrast with [[Complexity Zoo:S#s2p\|S<sub>2</sub>P]].

@@ Line 11: / Line 11: @@
 OIP = [[Complexity Zoo:I#ip|IP]] &#8745; [[Complexity Zoo:P#ppoly|P/poly]] [[zooref#gm15|[GM15]]].
 ===== <span id="oma" style="color:red">OMA</span>: Oblivious MA =====
@@ Line 28: / Line 30: @@
 Implicit in {{zcite|San07}} that OMA/1 (that is, OMA with 1 bit of trusted advice) does not have circuits of size <math>n^k</math> for any <math>k>0</math>.
 ===== <span id="onp" style="color:red">ONP</span>: Oblivious NP =====
@@ Line 48: / Line 52: @@
 See also [[Complexity Zoo:Y#yp|YP]] for an input oblivious analogue of [[Complexity Zoo:N#npiconp|NP &#8745; coNP]].
 ===== <span id="optp" style="color:red">OptP</span>: Optimum Polynomial-Time =====
@@ Line 57: / Line 63: @@
 [[MaxSat]] that returns the number of satisfied clauses, [[Clicque]] that returns the size of the clique, [[Chromatic Number]] are OptP[log n]-complete.
 ===== <span id="o2p" style="color:red">O<sub>2</sub>P</span>: Second Level of the Oblivious Symmetric Hierarchy  =====

← Older revision		Revision as of 20:30, 8 December 2023
Line 71:		Line 71:

	Contains [[Complexity Zoo:O#onp\|ONP]] and coONP [[zooref#gm15\|[GM15]]].		Contains [[Complexity Zoo:O#onp\|ONP]] and coONP [[zooref#gm15\|[GM15]]].
		+
		+	Does not have any fixed polynomial sized circuits [[zooref#li23\|[Li23]]].

	Contrast with [[Complexity Zoo:S#s2p\|S<sub>2</sub>P]].		Contrast with [[Complexity Zoo:S#s2p\|S<sub>2</sub>P]].

@@ Line 50: / Line 50: @@
 ===== <span id="optp" style="color:red">OptP</span>: Optimum Polynomial-Time =====
-The class of functions computable by taking the maximum of the output values over all accepting paths of an [[Complexity Zoo:N#np|NP]] machine.
+The class of functions computable by taking the maximum (or minimum) of the output values over all accepting paths of an [[Complexity Zoo:N#np|NP]] machine. OptP[f(n)] restricts the size of the output to f(n) bits.
 Defined in [[zooref#kre88|[Kre88]]].
 Contrast with [[Complexity Zoo:F#fnp|FNP]].
 ===== <span id="o2p" style="color:red">O<sub>2</sub>P</span>: Second Level of the Oblivious Symmetric Hierarchy  =====

← Older revision		Revision as of 23:27, 23 August 2022
Line 26:		Line 26:

	[[Complexity Zoo:B#bpp\|BPP]] is contained in OMA [[zooref#gm15\|[GM15]]].		[[Complexity Zoo:B#bpp\|BPP]] is contained in OMA [[zooref#gm15\|[GM15]]].
		+
		+	Implicit in {{zcite\|San07}} that OMA/1 (that is, OMA with 1 bit of trusted advice) does not have circuits of size <math>n^k</math> for any <math>k>0</math>.

	===== <span id="onp" style="color:red">ONP</span>: Oblivious NP =====		===== <span id="onp" style="color:red">ONP</span>: Oblivious NP =====

← Older revision		Revision as of 22:03, 27 May 2021
Line 65:		Line 65:

	Defined in [[zooref#cr06\|[CR06]]], where it was shown (among other properties) that O<sub>2</sub>P is self-low, and that the Karp-Lipton collapse goes all the way down to O<sub>2</sub>P: if [[Complexity Zoo:N#np\|NP]] is contained in [[Complexity Zoo:P#ppoly\|P/poly]] then [[Complexity Zoo:P#ph\|PH]] = O<sub>2</sub>P.		Defined in [[zooref#cr06\|[CR06]]], where it was shown (among other properties) that O<sub>2</sub>P is self-low, and that the Karp-Lipton collapse goes all the way down to O<sub>2</sub>P: if [[Complexity Zoo:N#np\|NP]] is contained in [[Complexity Zoo:P#ppoly\|P/poly]] then [[Complexity Zoo:P#ph\|PH]] = O<sub>2</sub>P.
		+
		+	Contains [[Complexity Zoo:O#onp\|ONP]] and coONP [[zooref#gm15\|[GM15]]].

	Contrast with [[Complexity Zoo:S#s2p\|S<sub>2</sub>P]].		Contrast with [[Complexity Zoo:S#s2p\|S<sub>2</sub>P]].