S2P (complexity)

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 Σ 2 P and Π 2 P , it also follows immediately that SP
2 is contained in Σ 2 P ∩ Π 2 P . This inclusion can in fact be strengthened to ZPP^NP.

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 Δ 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 Template:San-serif(n^k) 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.