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 S_2^P if there exists a polynomial-time predicate P such that

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 ZPPNP.[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^{S_2^P}=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 SIZE(nk) for any fixed k.

Symmetric hierarchy

As an extension, it is possible to define S_2 as an operator on complexity classes; then S_2 P = 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

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

External links

This article is issued from Wikipedia - version of the Thursday, October 29, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.