Suppose a polynomial-time computable judge has to decide whether a string is in a language. Two lawyers submit written arguments to convince the judge, one arguing for the string in the language and the other arguing for the string to be out of the language. Neither lawyer can see the others arguments. For what languages can we have the judge always convinced?

Russell
and Sundaram define the class S_{2}^{P} to capture this notion. Formally
a language L is in S_{2}^{P} if there is a polynomial-time predicate A and
a polynomial q such that

- If x is in L then there is a y such that for all z, A(x,y,z).
- If x is not in L then there is a z such that for all y, not A(x,y,z).

Personally I like to think
of S_{2}^{P} as for every input x defining an
exponential binary matrix A where the (i,j) entry of A is computable
in polynomial time from i,j and x. If x is in the language then A has
a row of all ones. If x is not in the language then A has a column of
all zeros.

NP∪coNP is in S_{2}^{P} is in
Σ_{2}^{P}∩Π_{2}^{P}.
Russell and Sundaram show that S_{2}^{P} is closed
under Turing reduction and relativizations to BPP. This implies BPP,
MA and P^{NP} are contained in S_{2}^{P}.

A big breakthrough for S_{2}^{P} comes from Cai
who shows that S_{2}^{P} is contained in
ZPP^{NP}. His proof is builds on the learning
algorithm of Bshouty, et. al. Sengupta noticed that a variation
of the
Karp-Lipton result shows that if NP has polynomial-size circuits
then the polynomial-time hierarchy collapses to
S_{2}^{P}. This also improves Kannan's
result to show that for any fixed k, there is a language in
S_{2}^{P} that does not have n^{k}-size
circuits. S_{2}^{P} is the smallest class known to have these properties.

S_{2}^{P} has come up recently in several of my research projects. Beigel,
Buhrman, Fejer, Fortnow, Longpre, Stephan and Torenvliet show that
a language L is in S_{2}^{P} if and only if there is a function f mapping
Σ^{*} to {1,2,3} such that L is polynomial-time Turing
reducible to all 2-enumerators for f. Buhrman and Fortnow give an
oracle separating ZPP^{NP} from Σ_{2}^{P}∩Π_{2}^{P} which by Cai's result
gives the first relativized world separating S_{2}^{P} from
Σ_{2}^{P}∩Π_{2}^{P}. Fortnow, Pavan and Sengupta show that if P^{NP[2]} =
P^{NP[1]} then the polynomial-time hierarchy collapses to
S_{2}^{P} improving on earlier collapses. You will have to trust me on the
latter two results as they are in the process of being written up.

Whether S_{2}^{P} contains ZPP^{NP} is open
even for relativized worlds. Since AM∩coAM is in ZPP^{NP},
one could try to prove that AM∩coAM is in
S_{2}^{P} or a specific language in AM∩coAM such
as graph isomorphism.

There are variations on the class S_{2}^{P} and I
recommend reading the papers of Russell
and Sundaram and Cai
for these and other results about this interesting class.

I could't solve the problem.

ReplyDeleteAnyway, it's very tricky to determine the difficulty of the problem.

I once saw a similar problem wich couldn't be solved by several computerscience students. 2 friends of me wich are literature teachers were able to solve the problem within minutes. At least one of those friends couldn't solve this problem:

http://www.mathcats.com/explore/river/crossing.html

Thinking of numbers as words is not

"outside the box thinking" for someone with a literature background. For a computerscience

person it needs an ingenious moment to do so.