S2P (complexity)

In computational complexity theory, S is a complexity class, intermediate between the first and second levels of the polynomial hierarchy. A language is in $\mathsf 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 size of ''y'' and ''z'' must be polynomial of ''x''.

Relationship to other complexity classes

It is immediate from the definition that S is closed under unions, intersections, and complements. Comparing the definition with that of $\Sigma_^P$ and $\Pi_^P$, it also follows immediately that S is contained in $\Sigma_^P \cap \Pi_^P$. This inclusion can in fact be strengthened to ZPP^NP.. A preliminary version of this paper appeared earlier, in FOCS 2001, , , .

Every language in NP also belongs to For by definition, a language ''L'' is in NP, if and only if there exists a polynomial-time verifier ''V''(''x'',''y''), such that for every ''x'' in ''L'' there exists ''y'' for which ''V'' answers true, and such that for every ''x'' not in ''L'', ''V'' always answers false. But such a verifier can easily be transformed into an predicate ''P''(''x'',''y'',''z'') for the same language that ignores ''z'' and otherwise behaves the same as ''V''. By the same token, co-NP belongs to These straightforward inclusions can be strengthened to show that the class contains MA (by a generalization of the Sipser–Lautemann theorem) and $\Delta_^P$ (more generally, $P^=\mathsf S_2^P$).

Karp–Lipton theorem

A version of Karp–Lipton theorem states that if every language in NP has polynomial size circuits then the polynomial time hierarchy collapses to S. This result yields a strengthening of Kannan's theorem: it is known that S is not contained in (''n''^''k'') for any fixed ''k''.

Symmetric hierarchy

As an extension, it is possible to define $\mathsf S_2$ as an operator on complexity classes; then $\mathsf S_2 P = \mathsf S_2^P$. Iteration of $S_2$ operator yields a "symmetric hierarchy"; the union of the classes produced in this way is equal to the Polynomial hierarchy.

References

*
*

External links

*{{CZoo, S₂P, S#s2p
Complexity Class of the Week: S₂^P
Lance Fortnow, August 28, 2002.

Complexity classes