The class of functions computable by taking the maximum of the output values over all accepting paths of an NP machine.
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.
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.
This page was last modified on 18 September 2015, at 15:59.
This page has been accessed 9,616 times.