# Difference between revisions of "Complexity Zoo:O"

(Added O2P) |
|||

Line 8: | Line 8: | ||

Contrast with [[Complexity Zoo:F#fnp|FNP]]. | 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 ===== | ||

+ | The class of decision problems for which there is a polynomial-time predicate P such that, for each length n, there exists y* and z* of length poly(n) such that for all x of length n | ||

+ | <ol> | ||

+ | <li>If the answer is 'yes,' for all z, P(x,y*,z) is true.</li> | ||

+ | <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. | ||

+ | |||

+ | 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. | ||

+ | |||

+ | 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. | ||

+ | |||

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

## Revision as of 19:59, 18 September 2015

*Back to the Main Zoo* -
*Complexity Garden* -
*Zoo Glossary* -
*Zoo References*

*Complexity classes by letter:*
Symbols -
A -
B -
C -
D -
E -
F -
G -
H -
I -
J -
K -
L -
M -
N -
O -
P -
Q -
R -
S -
T -
U -
V -
W -
X -
Y -
Z

*Lists of related classes:*
Communication Complexity -
Hierarchies -
Nonuniform

##### OptP: Optimum Polynomial-Time

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

Defined in [Kre88].

Contrast with FNP.

##### O_{2}P: Second Level of the Oblivious Symmetric Hierarchy

The class of decision problems for which there is a polynomial-time predicate P such that, for each length n, there exists y* and z* of length poly(n) such that for all x of length n

- If the answer is 'yes,' for all z, P(x,y*,z) is true.
- If the answer is 'no,' then for all y, P(x,y,z*) is false.

Note that this differs from S_{2}P in that the witnesses in each case must only depend on the length of the input, and not on the input itself.

Less formally, O_{2}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.

Defined in [CR06], where it was shown (among other properties) that O_{2}P is self-low, and that the Karp-Lipton collapse goes all the way down to O_{2}P: if NP is contained in P/poly then PH = O_{2}P.

Contrast with S_{2}P.