S2P (complexity)

In computational complexity theory, S{{su|p=P|b=2}} is a complexity class, intermediate between the first and second levels of the polynomial hierarchy. A language {{mvar|L}} 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{{su|p=P|b=2}} is closed under unions, intersections, and complements. Comparing the definition with that of $\Sigma_{2}^P$ and $\Pi_{2}^P$ , it also follows immediately that S{{su|p=P|b=2}} is contained in $\Sigma_{2}^P \cap \Pi_{2}^P$ . This inclusion can in fact be strengthened to ZPP^NP.{{citation

| last = Cai | first = Jin-Yi

| doi = 10.1016/j.jcss.2003.07.015

| issue = 1

| journal = Journal of Computer and System Sciences

| mr = 2279029

| pages = 25–35

| title = $\mathrm S_2^p \subseteq \mathrm{{ZPP}^{NP}}$

| url = http://pages.cs.wisc.edu/~jyc/papers/S2-j.pdf

| volume = 73

| year = 2007| doi-access = free

}}. A preliminary version of this paper appeared earlier, in FOCS 2001, {{ECCC|2001|01|030}}, {{MR|1948751}}, {{doi|10.1109/SFCS.2001.959938}}.

Every language in NP also belongs to {{nowrap|S{{su|p=P|b=2}}.}} 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 {{nowrap|S{{su|p=P|b=2}}}} 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 {{nowrap|S{{su|p=P|b=2}}.}} These straightforward inclusions can be strengthened to show that the class {{nowrap|S{{su|p=P|b=2}}}} contains MA (by a generalization of the Sipser–Lautemann theorem) and $\Delta_{2}^P$ (more generally, $P^{\mathsf S_2^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{{su|p=P|b=2}}. This result yields a strengthening of Kannan's theorem: it is known that S{{su|p=P|b=2}} is not contained in {{sans-serif|SIZE}}(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

{{cite journal | title=More on BPP and the polynomial-time hierarchy | first=Ran | last=Canetti | journal=Information Processing Letters | volume=57 | number=5 | pages=237–241 | year=1996 | publisher=Elsevier | doi=10.1016/0020-0190(96)00016-6}}
{{cite journal | year=1998 | issn=1016-3328 | journal=Computational Complexity | volume=7 | number=2 | doi=10.1007/s000370050007 | title=Symmetric alternation captures BPP | publisher=Birkhäuser Verlag | first1=Alexander | last1=Russell | first2=Ravi | last2=Sundaram | pages=152–162| s2cid=15331219 }}

External links

{{CZoo|S₂P|S#s2p}}
[http://blog.computationalcomplexity.org/2002/08/complexity-class-of-week-s2p.html Complexity Class of the Week: S₂^P], Lance Fortnow, August 28, 2002.

Category:Complexity classes