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.

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 ZPP^NP.

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(n^k) 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

• 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: S₂P
• Complexity Class of the Week: S₂^P, Lance Fortnow, August 28, 2002.