S2P (complexity)

In computational complexity theory, SP2 is a complexity class, intermediate between the first and second levels of the polynomial hierarchy. A language L is in S2P if there exists a polynomial-time predicate P such that

* If x∈L, then there exists a y such that for all z, P(x,y,z)=1,
* If x∉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.

## Contents

* 1 Relationship to other complexity classes
* 2 Karp–Lipton theorem
* 3 Symmetric hierarchy
* 4 References
* 5 External links

## Relationship to other complexity classes

It is immediate from the definition that SP2 is closed under unions, intersections, and complements. Comparing the definition with that of Σ2P and Π2P, it also follows immediately that SP2 is contained in Σ2P∩Π2P. This inclusion can in fact be strengthened to ZPPNP.[1]

Every language in NP also belongs to SP2. 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 SP2 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 SP2. These straightforward inclusions can be strengthened to show that the class SP2 contains MA (by a generalization of the Sipser–Lautemann theorem) and Δ2P (more generally, PS2P=S2P).

## 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 SP2. This result yields a strengthening of Kannan's theorem: it is known that SP2 is not contained in SIZE(nk) for any fixed k.

## Symmetric hierarchy

As an extension, it is possible to define S2 as an operator on complexity classes; then S2P=S2P. Iteration of S2 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), "S2p⊆ZPPNP", Journal of Computer and System Sciences 73 (1): 25–35, doi:10.1016/j.jcss.2003.07.015, http://pages.cs.wisc.edu/~jyc/papers/S2-j.pdf . A preliminary version of this paper appeared earlier, in FOCS 2001, ECCC TR01-030, MR1948751, doi:10.1109/SFCS.2001.959938.

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

## External links

* Complexity Zoo: S2P
* Complexity Class of the Week: S2P, Lance Fortnow, August 28, 2002.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/S2P (complexity). Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=S2P_(complexity)&oldid=316191"