1
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – J.Doe
    Commented Jun 1, 2023 at 15:40
  • 1
    $\begingroup$ 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? $\endgroup$
    – Lieuwe Vinkhuijzen
    Commented Jun 1, 2023 at 15:43
  • $\begingroup$ Yes it does! I was wondering how they assume $P$ and $x$ (silly but had to verify!). Thanks a ton again :) $\endgroup$
    – J.Doe
    Commented Jun 1, 2023 at 15:46
  • 1
    $\begingroup$ (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$. $\endgroup$
    – Lieuwe Vinkhuijzen
    Commented Jun 2, 2023 at 18:50
  • 1
    $\begingroup$ (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$. $\endgroup$
    – Lieuwe Vinkhuijzen
    Commented Jun 2, 2023 at 18:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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