<p>I will give an informal description, and then show how this description leads us to define the complexity class <span class="math-container">$S_2^P$</span>.</p>
<p><strong>Informal description as a one-round game.</strong> Let us first describe the class <span class="math-container">$NP$</span> as a one-round game whose participants are you and an untrusted prover. The prover is trying to convince you to accept the input. On input <span class="math-container">$x$</span>, the prover sends you a message <span class="math-container">$y$</span>, and you need to decide whether to accept the string <span class="math-container">$x$</span> or not. This is most clearly illustrated by thinking of the Hamiltonian path problem: on input a graph <span class="math-container">$G$</span>, if <span class="math-container">$G$</span> contains a Hamiltonian path, then the prover's job is easy: their message <span class="math-container">$y$</span> is just a description of that path. However, if <span class="math-container">$G$</span> contains no such path, then nothing the prover says can convince you.</p>
<p>Similarly, <span class="math-container">$S_2^P$</span> can be understood as a one-round game with three participants: you and two untrusted provers. One of the provers is trying to convince you to accept (just like in <span class="math-container">$NP$</span>), whereas the other prover is trying to convince you to reject. On input <span class="math-container">$x$</span>, the provers submit their proofs <span class="math-container">$y$</span> and <span class="math-container">$z$</span> to you (simultaneously and without communicating between themselves).</p>
<hr />
<p><strong>Obtaining a formal definition from first principles.</strong> Let us try to define the complexity class which captures the informal description above. The end result will of course be to the definition you have given in your question, but the goal is to derive it from first principles.</p>
<p>Let <span class="math-container">$x$</span> be the input, <span class="math-container">$y$</span> the Accept-prover's message, and <span class="math-container">$z$</span> the Reject-prover's message. If <span class="math-container">$x\in L$</span>, then we desire that some string <span class="math-container">$y$</span> is available to the Accept-prover, which we accept regardless of what the Reject-prover tells us; in symbols, we write this as:
<span class="math-container">$$\forall x:\text{if }x\in L\text{ then }\exists y:\forall z: P(x,y,z)\text{ accepts} $$</span>
Similarly, if <span class="math-container">$x\not\in L$</span>, then we should heed the Reject-prover's counsel <span class="math-container">$z$</span>, regardless of the message <span class="math-container">$y$</span> we receive from the Accept-prover, so:
<span class="math-container">$$ \forall x:\text{if }x\not\in L\text{ then }\exists z:\forall y: P(x,y,z)\text{ rejects}$$</span></p>
<p>If we double-check, then this is indeed exactly the definition of <span class="math-container">$S_2^P$</span>.</p>
<hr />
<p><strong>Relation to other classes.</strong> The class <span class="math-container">$O_2^P$</span> is like <span class="math-container">$S_2^P$</span>, except that the messages <span class="math-container">$y$</span> and <span class="math-container">$z$</span> that the provers send, do not depend on <span class="math-container">$x$</span>, but only on the <em>length</em> of the string <span class="math-container">$x$</span>.</p>
<p>The class <span class="math-container">$\Sigma_2^P$</span> is like <span class="math-container">$S_2^P$</span>, except that the Accept-prover sends their message <span class="math-container">$y$</span> before the Reject-prover does. This way, the Reject-prover can base their message <span class="math-container">$z$</span> on the message <span class="math-container">$y$</span>. The class <span class="math-container">$\Pi_2^P$</span> is similar, except that the Reject-prover moves first and the Accept-prover moves second.</p>

CC BY-SA 4.0
2023-06-01T15:40:45.113Z
Thank you for such a detailed and clear explanation. Extremely helpful and insightful. Just to reiterate/verify, an instance of a this language's problem would be then similar to the two player game as you described above as follows: The two players would be given an explicit function $P(x, y, z)$ representing some language $L$ and the two players would be asked if some $x$ is in $P(x, y, z)$ or not. Of course the 'proofs' by the players would have to satisfy the constraints as you described above. Is this correct?
J.Doe
CC BY-SA 4.0
2023-06-01T15:43:13.100Z
Thanks! I'm not 100% sure what you mean. I think you are asking whether the two provers know which algorithm $P$ you the verifier use? Yes, they know. They are given your algorithm. If you like, you can think of the game as taking place in three rounds, rather than one: first, (1) you give the provers your algorithm $P$. Then (2) the input $x$ appears. Lastly (3) both provers submit their proofs, and you execute algorithm $P$. Does this answer your question?
Lieuwe Vinkhuijzen
CC BY-SA 4.0
2023-06-01T15:46:27.847Z
Yes it does! I was wondering how they assume $P$ and $x$ (silly but had to verify!). Thanks a ton again :)
J.Doe
CC BY-SA 4.0
2023-06-02T17:13:58.233Z
just a follow up: As I thought about this class its obvious that there might be some $x$ that might not satisfy either constraint 1 or 2. So, $S_2^P$ by definition seems like a promise class i.e. input $x$ is always guaranteed to satisfy either 1 or 2. The definition doesn't mention it explicitly. Is that interpretation correct?
J.Doe
CC BY-SA 4.0
2023-06-02T18:50:27.103Z
(1/2) For a given predicate $P$, it is possible that $x$ satisfies neither condition, but this just means your polynomial-time predicate $P$ is not sound, since you can be fooled by one of the provers. So in this case either you need to find a better algorithm $P$, or your language $L$ is not in $S_2^P$, but no, $S_2^P$ is not a promise class. But let's take a step back. For a given problem (or "language") $L$, you want to know whether $L\in S_2^P$. This is true iff you can find an algorithm $P$ which performs the above game _for all $x$_. If no such $P$ exists, then $L\not\in S_2^P$.
Lieuwe Vinkhuijzen
CC BY-SA 4.0
2023-06-02T18:52:20.717Z
(2/2) Of course, it is also possible to define $\textsf{Promise}S_2^P$, as the set of tuples $(L_{yes},L_{no})$ such that there exists a predicate $P$ such that for each $x\in L_{yes}$, condition 1 holds, and for each $x\in L_{no}$, condition 2 holds, and having $L_{yes}\cap L_{no}=\emptyset$.
Lieuwe Vinkhuijzen
CC BY-SA 4.0
2023-06-01T15:13:02.420Z
2023-06-01T15:13:02.420Z
Lieuwe Vinkhuijzen
<p>I am trying to understand the complexity class <span class="math-container">$S_2^P$</span> defined as (<a href="https://en.wikipedia.org/wiki/S2P_(complexity)" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/S2P_(complexity)</a>). A language L is in <span class="math-container">$S_2^P$</span> if there exists a polynomial-time predicate <span class="math-container">$P$</span> such that:</p>
<ol>
<li>If <span class="math-container">$x\in L$</span>, then there exists a <span class="math-container">$y$</span> such that for all <span class="math-container">$z$</span>, <span class="math-container">$P(x,y,z)=1$</span>.</li>
<li>If <span class="math-container">$x\notin L$</span>, then there exists a <span class="math-container">$z$</span> such that for all <span class="math-container">$y$</span>, <span class="math-container">$P(x,y,z)=0$</span>.</li>
</ol>
<p>where size of <span class="math-container">$y$</span> and <span class="math-container">$z$</span> must be polynomial of <span class="math-container">$x$</span> (denoted by <span class="math-container">$q(|x|)$</span>).</p>
<p>I am clear with this definition. So will a typical problem be of the form:</p>
<p>For any given language predicate <span class="math-container">$P(x, y, z)$</span>, polynomial <span class="math-container">$q(|x|)$</span> and string <span class="math-container">$x$</span>, does <span class="math-container">$x\in L$</span> or <span class="math-container">$x\notin L$</span>? Is this interpretation correct? I couldn't find many resources on this class thus is trivial query.</p>

<cc.complexity-theory><complexity-classes>
Explanation of Complexity class $S_2^P$?
J.Doe
# Explanation of Complexity class $S_2^P$?

(Asked by: username_0 on 2023-06-01)

I am trying to understand the complexity class $S\_2^P$ defined as (<https://en.wikipedia.org/wiki/S2P_(complexity)>). A language L is in $S\_2^P$ if there exists a polynomial-time predicate $P$ such that:

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

where size of $y$ and $z$ must be polynomial of $x$ (denoted by $q(|x|)$).

I am clear with this definition. So will a typical problem be of the form:

For any given language predicate $P(x, y, z)$, polynomial $q(|x|)$ and string $x$, does $x\in L$ or $x\notin L$? Is this interpretation correct? I couldn't find many resources on this class thus is trivial query.

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


---

## 1 answers

### Answer by username_1 on 2023-06-01. Score: 4 | Accepted answer

I will give an informal description, and then show how this description leads us to define the complexity class $S\_2^P$.

**Informal description as a one-round game.** Let us first describe the class $NP$ as a one-round game whose participants are you and an untrusted prover. The prover is trying to convince you to accept the input. On input $x$, the prover sends you a message $y$, and you need to decide whether to accept the string $x$ or not. This is most clearly illustrated by thinking of the Hamiltonian path problem: on input a graph $G$, if $G$ contains a Hamiltonian path, then the prover's job is easy: their message $y$ is just a description of that path. However, if $G$ contains no such path, then nothing the prover says can convince you.

Similarly, $S\_2^P$ can be understood as a one-round game with three participants: you and two untrusted provers. One of the provers is trying to convince you to accept (just like in $NP$), whereas the other prover is trying to convince you to reject. On input $x$, the provers submit their proofs $y$ and $z$ to you (simultaneously and without communicating between themselves).

---

**Obtaining a formal definition from first principles.** Let us try to define the complexity class which captures the informal description above. The end result will of course be to the definition you have given in your question, but the goal is to derive it from first principles.

Let $x$ be the input, $y$ the Accept-prover's message, and $z$ the Reject-prover's message. If $x\in L$, then we desire that some string $y$ is available to the Accept-prover, which we accept regardless of what the Reject-prover tells us; in symbols, we write this as:
$$\forall x:\text{if }x\in L\text{ then }\exists y:\forall z: P(x,y,z)\text{ accepts} $$
Similarly, if $x\not\in L$, then we should heed the Reject-prover's counsel $z$, regardless of the message $y$ we receive from the Accept-prover, so:
$$ \forall x:\text{if }x\not\in L\text{ then }\exists z:\forall y: P(x,y,z)\text{ rejects}$$

If we double-check, then this is indeed exactly the definition of $S\_2^P$.

---

**Relation to other classes.** The class $O\_2^P$ is like $S\_2^P$, except that the messages $y$ and $z$ that the provers send, do not depend on $x$, but only on the *length* of the string $x$.

The class $\Sigma\_2^P$ is like $S\_2^P$, except that the Accept-prover sends their message $y$ before the Reject-prover does. This way, the Reject-prover can base their message $z$ on the message $y$. The class $\Pi\_2^P$ is similar, except that the Reject-prover moves first and the Accept-prover moves second.

> **Comments:**
> **username_0**: Thank you for such a detailed and clear explanation. Extremely helpful and insightful. Just to reiterate/verify, an instance of a this language's problem would be then similar to the two player game as you described above as follows: The two players would be given an explicit function $P(x, y, z)$ representing some language $L$ and the two players would be asked if some $x$ is in $P(x, y, z)$ or not. Of course the 'proofs' by the players would have to satisfy the constraints as you described above. Is this correct?  
> **username_1**: Thanks! I'm not 100% sure what you mean. I think you are asking whether the two provers know which algorithm $P$ you the verifier use? Yes, they know. They are given your algorithm. If you like, you can think of the game as taking place in three rounds, rather than one: first, (1) you give the provers your algorithm $P$. Then (2) the input $x$ appears. Lastly (3) both provers submit their proofs, and you execute algorithm $P$. Does this answer your question?  
> **username_0**: Yes it does! I was wondering how they assume $P$ and $x$ (silly but had to verify!). Thanks a ton again :)  
> **username_0**: just a follow up: As I thought about this class its obvious that there might be some $x$ that might not satisfy either constraint 1 or 2. So, $S_2^P$ by definition seems like a promise class i.e. input $x$ is always guaranteed to satisfy either 1 or 2. The definition doesn't mention it explicitly. Is that interpretation correct?  
> **username_1**: (1/2) For a given predicate $P$, it is possible that $x$ satisfies neither condition, but this just means your polynomial-time predicate $P$ is not sound, since you can be fooled by one of the provers. So in this case either you need to find a better algorithm $P$, or your language $L$ is not in $S_2^P$, but no, $S_2^P$ is not a promise class. But let's take a step back. For a given problem (or "language") $L$, you want to know whether $L\in S_2^P$. This is true iff you can find an algorithm $P$ which performs the above game _for all $x$_. If no such $P$ exists, then $L\not\in S_2^P$.  
> **username_1**: (2/2) Of course, it is also possible to define $\textsf{Promise}S_2^P$, as the set of tuples $(L_{yes},L_{no})$ such that there exists a predicate $P$ such that for each $x\in L_{yes}$, condition 1 holds, and for each $x\in L_{no}$, condition 2 holds, and having $L_{yes}\cap L_{no}=\emptyset$.  

---

