<p>Is there a decision problem in $\textsf{S}_2\textsf{P}$ that (presumably) requires the full power of $\textsf{S}_2\textsf{P}$-computations? Specifically, is there a language in $\textsf{S}_2\textsf{P}$ that doesn't obviously belong to any 'natural' smaller class? The two 'natural' classes that I have in mind are $\textsf{P}^{\textsf{NP}}$ and $\textsf{BPP}$.</p>

CC BY-SA 3.0
2018-02-07T14:42:48.800Z
Are you asking for a complete problem, or just for a natural problem not known to lie in any smaller natural class?
Joshua Grochow
CC BY-SA 3.0
2018-02-07T17:09:26.427Z
Under plausible assumptions, $\mathrm{P^{NP}=S_2P=ZPP^{NP}}$.
Emil Jeřábek
CC BY-SA 3.0
2018-02-07T17:18:57.123Z
@JoshuaGrochow the latter, a natural problem not known to lie in any smaller class.
Apoorva Bhagwat
CC BY-SA 3.0
2018-02-07T17:23:51.963Z
@EmilJeřábek I guess my question is analogous to the following - under plausible assumptions, $\textsf{BPP}=\textsf{P}$, yet we have a problem that's known to be in $\textsf{BPP}$ but not in $\textsf{P}$ (polynomial identity testing or something similar). Do we know a similar example for $\textsf{S}_2\textsf{P}$ and $\textsf{P}^{\textsf{NP}}$, even though they're plausibly equal?
Apoorva Bhagwat
CC BY-SA 3.0
2018-02-08T22:07:27.317Z
You might re-title your question as "Natural problem in S_2 P not known to be in any smaller class"
Joshua Grochow
CC BY-SA 3.0
2018-02-08T22:09:21.510Z
Also, asking for a problem not known to be in $\mathsf{P}^{\mathsf{NP}} \cup \mathsf{BPP}$ would be quite different, potentially, than asking for a problem not known to be in [$\mathsf{O_2 P}$](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:O) (which seems much closer to $\mathsf{S_2 P}$...
Joshua Grochow
CC BY-SA 3.0
2018-02-09T10:27:53.613Z
Another natural class included in S2P is $P^{MA}$ (which includes both BPP and $P^{NP}$).
Emil Jeřábek
CC BY-SA 3.0
2018-02-09T10:50:55.180Z
@Joshua Since O2P is included in P/poly, I'd say it's actually rather far from S2P.
Emil Jeřábek
CC BY-SA 3.0
2018-02-10T19:43:51.713Z
Yup, I think the reference in the answer to [A natural problem in $S_2^P$](http://cstheory.stackexchange.com/questions/17819) is a good starting point for me. Thank you!
Apoorva Bhagwat
<cc.complexity-theory>
Natural problem in S2P not known to be in any smaller class
Apoorva Bhagwat
# Natural problem in S2P not known to be in any smaller class

(Asked by: username_0 on 2018-02-06)

Is there a decision problem in $\textsf{S}\_2\textsf{P}$ that (presumably) requires the full power of $\textsf{S}\_2\textsf{P}$-computations? Specifically, is there a language in $\textsf{S}\_2\textsf{P}$ that doesn't obviously belong to any 'natural' smaller class? The two 'natural' classes that I have in mind are $\textsf{P}^{\textsf{NP}}$ and $\textsf{BPP}$.

**Tags:** cc.complexity-theory
> **Comments:**
> **username_1**: Are you asking for a complete problem, or just for a natural problem not known to lie in any smaller natural class?  
> **username_2**: Under plausible assumptions, $\mathrm{P^{NP}=S_2P=ZPP^{NP}}$.  
> **username_0**: @JoshuaGrochow the latter, a natural problem not known to lie in any smaller class.  
> **username_0**: @EmilJeřábek I guess my question is analogous to the following - under plausible assumptions, $\textsf{BPP}=\textsf{P}$, yet we have a problem that's known to be in $\textsf{BPP}$ but not in $\textsf{P}$ (polynomial identity testing or something similar). Do we know a similar example for $\textsf{S}_2\textsf{P}$ and $\textsf{P}^{\textsf{NP}}$, even though they're plausibly equal?  
> **username_1**: You might re-title your question as "Natural problem in S_2 P not known to be in any smaller class"  
> **username_1**: Also, asking for a problem not known to be in $\mathsf{P}^{\mathsf{NP}} \cup \mathsf{BPP}$ would be quite different, potentially, than asking for a problem not known to be in [$\mathsf{O_2 P}$](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:O) (which seems much closer to $\mathsf{S_2 P}$...  
> **username_2**: Another natural class included in S2P is $P^{MA}$ (which includes both BPP and $P^{NP}$).  
> **username_2**: @Joshua Since O2P is included in P/poly, I'd say it's actually rather far from S2P.  
> **username_0**: Yup, I think the reference in the answer to [A natural problem in $S_2^P$](http://cstheory.stackexchange.com/questions/17819) is a good starting point for me. Thank you!  

---

## 0 answers

