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

---

OIP - OMA - ONP - OptP - O₂P

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₂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

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

Note that this differs from S₂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₂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₂P is self-low, and that the Karp-Lipton collapse goes all the way down to O₂P: if NP is contained in P/poly then PH = O₂P.

Contrast with S₂P.