# A natural problem in $\textrm{S}_2^\textrm{P}$?

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}$.

• How about "an odd number of these circuits are satisfiable"? $\;$
– user6973
May 29 '13 at 5:35
• This is a nice example, however, it is also in the smaller class $\Delta_2 = \mathsf{P}^{\mathsf{NP}}$. May 29 '13 at 9:28
• 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 May 29 '13 at 16:43
• @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.) May 29 '13 at 21:16
• @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. May 29 '13 at 21:18

How about a problem complete for promise-$\mathsf{S_2^p}$?
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.)