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

OMA: Oblivious MA

The class of functions computable in randomized polynomial time with a shared, untrusted witness for each input size. The input-oblivious version of MA.

L is in OMA if there exists a randomized, polynomial time verifier V taking an input and a witness, so that:

1. There is a witness for each n of polynomial size, so that for any input of size n, if the answer is "yes," then the verifier accepts on that input and the witness.
2. If the answer for an input is "no," then for any witness, the verifier rejects on that input with probability at least 1/2.

NP is contained in OMA iff NP is in P/poly [FSW09].

EXP is contained in P/poly iff EXP = OMA [FSW09].

BPP is contained in OMA [GM15].

ONP: Oblivious NP

The class of functions computable in polynomial time with a shared, untrusted witness for each input size. The input-oblivious version of NP.

L is in ONP if there exists a polynomial time verifier V taking an input and a witness, so that:

1. There is a witness for each n of polynomial size, so that for any input of size n, if the answer is "yes," then the verifier accepts on that input and the witness.
2. If the answer for an input is "no," then for any witness, the verifier rejects on that input.

Defined in [FSW09], where it was shown NP has size n^k circuits for some constant k if and only if ONP/1 has size n^j circuits for some constant j.

ONP is contained in P/poly and NP [FSW09].

ONP = NP iff NP is in P/poly [FSW09].

If NE is not E then ONP is not P [GM15].

See also YP for an input oblivious analogue of NP ∩ coNP.

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.