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 [math]\displaystyle{ \mathsf S_2^P }[/math] if there exists a polynomial-time predicate P such that

* If [math]\displaystyle{ x \in L }[/math], then there exists a y such that for all z, [math]\displaystyle{ P(x,y,z)=1 }[/math],
* If [math]\displaystyle{ x \notin L }[/math], then there exists a z such that for all y, [math]\displaystyle{ P(x,y,z)=0 }[/math],

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 [math]\displaystyle{ \Sigma_{2}^P }[/math] and [math]\displaystyle{ \Pi_{2}^P }[/math], it also follows immediately that SP2 is contained in [math]\displaystyle{ \Sigma_{2}^P \cap \Pi_{2}^P }[/math]. 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 [math]\displaystyle{ \Delta_{2}^P }[/math] (more generally, [math]\displaystyle{ P^{\mathsf S_2^P}=\mathsf S_2^P }[/math]).

## 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 [math]\displaystyle{ \mathsf S_2 }[/math] as an operator on complexity classes; then [math]\displaystyle{ \mathsf S_2 P = \mathsf S_2^P }[/math]. Iteration of [math]\displaystyle{ S_2 }[/math] 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), "[math]\displaystyle{ \mathrm S_2^p \subseteq \mathrm{{ZPP}^{NP}} }[/math]", 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=123666"