# Difference between revisions of "Complexity Zoo:O"

(3 intermediate revisions by the same user not shown) | |||

Line 1: | Line 1: | ||

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

+ | ===== <span id="oip" style="color:red">OIP</span>: Oblivious IP ===== | ||

+ | [[Complexity Zoo:I#ip|IP]] where only the input size is known during the interaction with the prover, and after that interaction, the verifier gets the specific input. | ||

+ | L is in OIP if there exists a randomized, polynomial time interrogator I which takes an input size and interacts with a prover to produce a witness, and polynomial time verifier V that takes an input and a witness so that | ||

+ | <ol> | ||

+ | <li>Given an input size n, there is prover so that I given n and interacting with the prover produces a witness w so that, for any input x of length n where x is in L, V accepts on x and w.</li> | ||

+ | <li>For any x not in L of length n, for any prover interacting with I on input n gives a witness w' which V will reject with x and w' with probability at least 2/3.</li> | ||

+ | </ol> | ||

+ | |||

+ | OIP = [[Complexity Zoo:I#ip|IP]] ∩ [[Complexity Zoo:P#ppoly|P/poly]] [[zooref#gm15|[GM15]]]. | ||

+ | |||

+ | ===== <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 input is is in L, then the verifier accepts on that input and the witness.</li> | ||

+ | <li>If the input is not in L, 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 ===== | ||

− | The class of functions computable in polynomial time with a shared, untrusted witness for each input size. The input-oblivious version of [[Complexity Zoo: | + | The class of functions computable in polynomial time with a shared, untrusted witness for each input size. The input-oblivious version of [[Complexity Zoo:N#np|NP]]. |

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

<ol> | <ol> | ||

− | <li>There is a witness for each n of polynomial size, so that for any input of size n, if the | + | <li>There is a witness for each n of polynomial size, so that for any input of size n, if the input is in L, then the verifier accepts on that input and the witness.</li> |

− | <li>If the | + | <li>If the input is not in L, then for any witness, the verifier rejects on that input.</li> |

</ol> | </ol> | ||

− | Defined in [[zooref#fsw09|[FSW09]]], where it was shown [[Complexity Zoo: | + | 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 contained in [[Complexity Zoo:P#ppoly|P/poly]] and [[Complexity Zoo:N#np|NP]] [[zooref#fsw09|[FSW09]]]. | ||

− | ONP is in [[Complexity Zoo: | + | 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]]]. | |

+ | |||

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

Line 37: | Line 65: | ||

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

+ | |||

+ | Contains [[Complexity Zoo:O#onp|ONP]] and coONP [[zooref#gm15|[GM15]]]. | ||

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

## Revision as of 22:03, 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

##### OIP: Oblivious IP

IP where only the input size is known during the interaction with the prover, and after that interaction, the verifier gets the specific input.

L is in OIP if there exists a randomized, polynomial time interrogator I which takes an input size and interacts with a prover to produce a witness, and polynomial time verifier V that takes an input and a witness so that

- Given an input size n, there is prover so that I given n and interacting with the prover produces a witness w so that, for any input x of length n where x is in L, V accepts on x and w.
- For any x not in L of length n, for any prover interacting with I on input n gives a witness w' which V will reject with x and w' with probability at least 2/3.

##### 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 input is is in L, then the verifier accepts on that input and the witness.
- If the input is not in L, 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 input is in L, then the verifier accepts on that input and the witness.
- If the input is not in L, 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.

Contains ONP and coONP [GM15].

Contrast with S_{2}P.