# Complexity Zoo:O

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