Computational Complexity

Wednesday, August 28, 2002

 
Complexity Class of the Week: S₂^P

Posted by Lance

CCW Intro

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₂^P to capture this notion. Formally a language L is in S₂^P if there is a polynomial-time predicate A and a polynomial q such that

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

where |y| and |z| are bounded by q(|x|).

Personally I like to think of S₂^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₂^P is in Σ₂^P∩Π₂^P. Russell and Sundaram show that S₂^P is closed under Turing reduction and relativizations to BPP. This implies BPP, MA and P^NP are contained in S₂^P.

A big breakthrough for S₂^P comes from Cai who shows that S₂^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₂^P. This also improves Kannan's result to show that for any fixed k, there is a language in S₂^P that does not have n^k-size circuits. S₂^P is the smallest class known to have these properties.

S₂^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₂^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 Σ₂^P∩Π₂^P which by Cai's result gives the first relativized world separating S₂^P from Σ₂^P∩Π₂^P. Fortnow, Pavan and Sengupta show that if P^NP[2] = P^NP[1] then the polynomial-time hierarchy collapses to S₂^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₂^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₂^P or a specific language in AM∩coAM such as graph isomorphism.

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

2:07 PM # 0 comments

Comment Feeds: This Post All