S2P (complexity)

In computational complexity theory, STemplate:Su is a complexity class, intermediate between the first and second levels of the polynomial hierarchy. A language Template:Mvar is in ${𝖲}_2^P$ if there exists a polynomial-time predicate P such that

• If $x\in L$, then there exists a y such that for all z, $P(x,y,z)=1$,
• If $x\notin 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.

Relationship to other complexity classes

It is immediate from the definition that STemplate:Su is closed under unions, intersections, and complements. Comparing the definition with that of ${\mathrm{\Sigma }}_2^P$ and ${\mathrm{\Pi }}_2^P$, it also follows immediately that STemplate:Su is contained in ${\mathrm{\Sigma }}_2^P\cap {\mathrm{\Pi }}_2^P$. This inclusion can in fact be strengthened to ZPP^NP.

Every language in NP also belongs to Template:Nowrap 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 Template:Nowrap 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 Template:Nowrap These straightforward inclusions can be strengthened to show that the class Template:Nowrap contains MA (by a generalization of the Sipser–Lautemann theorem) and ${\mathrm{\Delta }}_2^P$ (more generally, $P^{{𝖲}_2^P}={𝖲}_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 STemplate:Su. This result yields a strengthening of Kannan's theorem: it is known that STemplate:Su is not contained in Template:Sans-serif(n^k) for any fixed k.

Symmetric hierarchy

As an extension, it is possible to define ${𝖲}_2$ as an operator on complexity classes; then ${𝖲}_{2}P={𝖲}_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

• Template:Cite journal
• Template:Cite journal

External links

• Template:CZoo
• Complexity Class of the Week: S₂^P, Lance Fortnow, August 28, 2002.