S2P (complexity)

In computational complexity theory, SP
2 is a complexity class, intermediate between the first and second levels of the polynomial hierarchy. A language $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 SP
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 SP
2 is contained in $\Sigma _{{2}}^{P}\cap \Pi _{{2}}^{P}$ . This inclusion can in fact be strengthened to ZPP^NP.^[1]

Every language in NP also belongs to SP
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 SP
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 SP
2. These straightforward inclusions can be strengthened to show that the class SP
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 SP
2. This result yields a strengthening of Kannan's theorem: it is known that SP
2 is not contained in Template:San-serif(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

↑ Cai, Jin-Yi (2007), " $\mathrm {S} _{2}^{p}\subseteq \mathrm {{ZPP}^{NP}}$ " (PDF), Journal of Computer and System Sciences, 73 (1): 25–35, MR 2279029, doi:10.1016/j.jcss.2003.07.015 . A preliminary version of this paper appeared earlier, in FOCS 2001, ECCC TR01-030, MR 1948751, doi:10.1109/SFCS.2001.959938.

Canetti, Ran (1996). "More on BPP and the polynomial-time hierarchy". Information Processing Letters. 57 (5). Elsevier. pp. 237–241. doi:10.1016/0020-0190(96)00016-6.
Russell, Alexander; Sundaram, Ravi (1998). "Symmetric alternation captures BPP". computational complexity. 7 (2). Birkhäuser Verlag. pp. 152–162. ISSN 1016-3328. doi:10.1007/s000370050007.

External links

Complexity Zoo: S₂P
Complexity Class of the Week: S₂^P, Lance Fortnow, August 28, 2002.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.