10
$\begingroup$

The complexity class $\textrm{S}_2^\textrm{P}$ is defined as follows (from Wikipedia):

A language $L$ is in $S_2^P$ if there exists a polynomial-time predicate $P$ such that

  • If $x \in L$, then there exists a $y$ such that for all $z$, $P(x,y,z)=1$
  • If $x \notin L$, then there exists a $z$ such that for all $y$, $P(x,y,z)=0$

where the size of both $y$ and $z$ must be polynomial in the size of $x$.

Also see Fortnow's post and the complexity zoo for more informal explanations and discussions.

While this class seems reasonably natural, I can't find an example of a problem that's in $\textrm{S}_2^\textrm{P}$ for a non-trivial reason (i.e., not just because it is in NP or MA or some class contained in $\textrm{S}_2^\textrm{P}$). Does anyone know a problem that fits this description?

If no one can think of a problem like that, I wouldn't mind a problem that's in a sub-class of $\textrm{S}_2^\textrm{P}$, but it's non-trivial to show this, whereas the problem is obviously in $\textrm{S}_2^\textrm{P}$.

$\endgroup$
  • 3
    $\begingroup$ How about "an odd number of these circuits are satisfiable"? $\;$ $\endgroup$ – user6973 May 29 '13 at 5:35
  • 3
    $\begingroup$ This is a nice example, however, it is also in the smaller class $\Delta_2 = \mathsf{P}^{\mathsf{NP}}$. $\endgroup$ – sdcvvc May 29 '13 at 9:28
  • 4
    $\begingroup$ Not quite what you asked for, but how about a problem complete for promise-$\mathsf{S_2^p}$? Fortnow--Impagliazzo--Kabanets--Umans, On the complexity of succinct zero-sum games, Computational Complexity 17:353-376, 2008, see cs.sfu.ca/~kabanets/Research/games.html $\endgroup$ – Joshua Grochow May 29 '13 at 16:43
  • 1
    $\begingroup$ @RickyDemer: Thanks, that's a nice example. (If I understand correctly, it's equally easy to show that the problem is in $\Delta_2$ too.) $\endgroup$ – Robin Kothari May 29 '13 at 21:16
  • $\begingroup$ @JoshuaGrochow: Thanks, that works for me. Feel free to post that as an answer. It seems like the best answer so far, but I'll wait to see if I get a better one. $\endgroup$ – Robin Kothari May 29 '13 at 21:18
8
$\begingroup$

How about a problem complete for promise-$\mathsf{S_2^p}$?

Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, and Chris Umans. On the complexity of succinct zero-sum games. Computational Complexity 17:353-376, 2008.

From the abstract:

We prove that approximating the value of a succinct zero-sum game to within an additive factor is complete for the class promise-$\mathsf{S_2^p}$, the "promise" version of $\mathsf{S_2^p}$. To the best of our knowledge, it is the first natural problem shown complete for this class.

(Historical note: it is not too surprising that not many natural problems are known to be in $\mathsf{S_2^p}$ but not known to be in its subclasses $\mathsf{MA}$ or $\mathsf{P^{NP}}$. If you check the original papers of Russell--Sundaram and Canetti (independently), it seems as though the definition of $\mathsf{S_2^p}$ was made more or less specifically to capture their improved arguments placing $\mathsf{BPP}$ in $\mathsf{PH}$, rather than to capture some set of of natural problems.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.