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

<p>Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, and Chris Umans. <a href="http://www.cs.sfu.ca/~kabanets/Research/games.html">On the complexity of succinct zero-sum games</a>. Computational Complexity 17:353-376, 2008. </p>

<p>From the abstract:</p>

<blockquote>
  <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.</p>
</blockquote>

<p>(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.)</p>

CC BY-SA 3.0
2013-05-30T05:46:01.680Z
2013-05-30T05:46:01.680Z
Joshua Grochow
<p>The complexity class $\textrm{S}_2^\textrm{P}$ is defined as follows (from <a href="http://en.wikipedia.org/wiki/S2P_%28complexity%29" rel="noreferrer">Wikipedia</a>):</p>

<blockquote>
  <p>A language $L$ is in $S_2^P$ if there exists a polynomial-time predicate $P$ such that</p>
  
  <ul>
  <li>If $x \in L$, then there exists a $y$ such that for all $z$, $P(x,y,z)=1$</li>
  <li>If $x \notin L$, then there exists a $z$ such that for all $y$, $P(x,y,z)=0$</li>
  </ul>
  
  <p>where the size of both $y$ and $z$ must be polynomial in the size of $x$.</p>
</blockquote>

<p>Also see <a href="http://blog.computationalcomplexity.org/2002/08/complexity-class-of-week-s2p.html" rel="noreferrer">Fortnow's post</a> and the <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aS#s2p" rel="noreferrer">complexity zoo</a> for more informal explanations and discussions.</p>

<p>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?</p>

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

CC BY-SA 3.0
2013-05-29T09:28:29.537Z
This is a nice example, however, it is also in the smaller class $\Delta_2 = \mathsf{P}^{\mathsf{NP}}$.
sdcvvc
CC BY-SA 3.0
2013-05-29T16:43:29.473Z
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 http://www.cs.sfu.ca/~kabanets/Research/games.html
Joshua Grochow
CC BY-SA 3.0
2013-05-29T21:16:35.043Z
@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.)
Robin Kothari
CC BY-SA 3.0
2013-05-29T21:18:26.487Z
@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.
Robin Kothari
<cc.complexity-theory><complexity-classes>
A natural problem in $\textrm{S}_2^\textrm{P}$?
Robin Kothari
# A natural problem in $\textrm{S}_2^\textrm{P}$?

(Asked by: username_0 on 2013-05-29)

The complexity class $\textrm{S}\_2^\textrm{P}$ is defined as follows (from [Wikipedia](http://en.wikipedia.org/wiki/S2P_%28complexity%29)):

> 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](http://blog.computationalcomplexity.org/2002/08/complexity-class-of-week-s2p.html) and the [complexity zoo](https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aS#s2p) 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}$.

**Tags:** cc.complexity-theory, complexity-classes

> **Comments:**
> **username_1**: This is a nice example, however, it is also in the smaller class $\Delta_2 = \mathsf{P}^{\mathsf{NP}}$.  
> **username_2**: 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 http://www.cs.sfu.ca/~kabanets/Research/games.html  
> **username_0**: @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.)  
> **username_0**: @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.  

---

## 1 answers

### Answer by username_2 on 2013-05-30. Score: 9 | Accepted answer

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](http://www.cs.sfu.ca/~kabanets/Research/games.html). 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.)


---

