# Difference between revisions of "Complexity Zoo:O"

Line 1: | Line 1: | ||

{{CZ-Letter-Menu|O}} | {{CZ-Letter-Menu|O}} | ||

+ | ===== <span id="oma" style="color:red">OMA</span>: 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 [[Complexity Zoo:M#ma|MA]]. | ||

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

+ | <ol> | ||

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

+ | <li>If the answer for an input is "no," then for any witness, the verifier rejects on that input with probability at least 1/2.</li> | ||

+ | </ol> | ||

+ | |||

+ | [[Complexity Zoo:N#np|NP]] is contained in OMA iff [[Complexity Zoo:N#np|NP]] is in [[Complexity Zoo:P#ppoly|P/poly]] [[zooref#fsw09|[FSW09]]]. | ||

+ | |||

+ | [[Complexity Zoo:E#exp|EXP]] is contained in [[Complexity Zoo:P#ppoly|P/poly]] iff [[Complexity Zoo:E#exp|EXP]] = OMA [[zooref#fsw09|[FSW09]]]. | ||

+ | |||

+ | [[Complexity Zoo:B#bpp|BPP]] is contained in OMA [[zooref#gm15|[GM15]]]. | ||

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

Line 15: | Line 28: | ||

Defined in [[zooref#fsw09|[FSW09]]], where it was shown [[Complexity Zoo:N#np|NP]] has size n<sup>k</sup> circuits for some constant k if and only if ONP/1 has size n<sup>j</sup> circuits for some constant j. | Defined in [[zooref#fsw09|[FSW09]]], where it was shown [[Complexity Zoo:N#np|NP]] has size n<sup>k</sup> circuits for some constant k if and only if ONP/1 has size n<sup>j</sup> circuits for some constant j. | ||

− | ONP is in [[Complexity Zoo:P#ppoly|P/poly]] [[zooref#fsw09|[FSW09]]] | + | ONP is contained in [[Complexity Zoo:P#ppoly|P/poly]] and [[Complexity Zoo:N#np|NP]] [[zooref#fsw09|[FSW09]]]. |

ONP = [[Complexity Zoo:N#np|NP]] iff [[Complexity Zoo:N#np|NP]] is in [[Complexity Zoo:P#ppoly|P/poly]] [[zooref#fsw09|[FSW09]]]. | ONP = [[Complexity Zoo:N#np|NP]] iff [[Complexity Zoo:N#np|NP]] is in [[Complexity Zoo:P#ppoly|P/poly]] [[zooref#fsw09|[FSW09]]]. | ||

If [[Complexity Zoo:N#ne|NE]] is not [[Complexity Zoo:E#e|E]] then ONP is not [[Complexity Zoo:P#p|P]] [[zooref#gm15|[GM15]]]. | If [[Complexity Zoo:N#ne|NE]] is not [[Complexity Zoo:E#e|E]] then ONP is not [[Complexity Zoo:P#p|P]] [[zooref#gm15|[GM15]]]. | ||

+ | |||

+ | See also [[Complexity Zoo:Y#yp|YP]] for an input oblivious analogue of [[Complexity Zoo:N#npiconp|NP ∩ coNP]]. | ||

===== <span id="optp" style="color:red">OptP</span>: Optimum Polynomial-Time ===== | ===== <span id="optp" style="color:red">OptP</span>: Optimum Polynomial-Time ===== |

## Revision as of 21:32, 27 May 2021

*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

##### 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:

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

- 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.
- 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_{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.