Difference between revisions of "Complexity Zoo:O"
Emil Jeřábek (talk | contribs) (→O2P: Second Level of the Oblivious Symmetric Hierarchy: mention inclusion in P/poly) |
|||
| (4 intermediate revisions by one other 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 32: | Line 60: | ||
<li>If the answer is 'no,' then for all y, P(x,y,z*) is false.</li> | <li>If the answer is 'no,' then for all y, P(x,y,z*) is false.</li> | ||
</ol> | </ol> | ||
| − | Note that this differs from [[#s2p|S<sub>2</sub>P]] in that the witnesses in each case must only depend on the length of the input, and not on the input itself. | + | Note that this differs from [[#s2p|S<sub>2</sub>P]] in that the witnesses in each case must only depend on the length of the input, and not on the input itself. In particular, since the conditions imply that the answer is 'yes' iff P(x,y*,z*), the class O<sub>2</sub>P is included in [[Complexity Zoo:P#ppoly|P/poly]]. |
Less formally, O<sub>2</sub>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. | Less formally, O<sub>2</sub>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 [[zooref#cr06|[CR06]]], where it was shown (among other properties) that O<sub>2</sub>P is self-low, and that the | + | 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 18:54, 6 July 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 nk circuits for some constant k if and only if ONP/1 has size nj 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.
O2P: 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 S2P in that the witnesses in each case must only depend on the length of the input, and not on the input itself. In particular, since the conditions imply that the answer is 'yes' iff P(x,y*,z*), the class O2P is included in P/poly.
Less formally, O2P 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 O2P is self-low, and that the Karp–Lipton collapse goes all the way down to O2P: if NP is contained in P/poly then PH = O2P.
Contains ONP and coONP [GM15].
Contrast with S2P.