# Difference between revisions of "Complexity Zoo:O"

(Added O2P) |
|||

Line 1: | Line 1: | ||

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

+ | |||

+ | |||

+ | ===== <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:F#np|NP]]. | ||

+ | |||

+ | L is in ONP if there exists a 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.</li> | ||

+ | </ol> | ||

+ | |||

+ | Defined in [[zooref#fsw09|[FSW09]]], where it was shown [[Complexity Zoo:F#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:F#ppoly|P/poly]] [[zooref#fsw09|[FSW09]]] | ||

+ | |||

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

===== <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 18:02, 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

##### 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 = NP iff NP is in P/poly [FSW09].

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