In computational complexity theory, \( {\mathsf {S}}_{2}^{P}} \) is a complexity class, intermediate between the first and second levels of the polynomial hierarchy. A language L is in \( {\displaystyle {\mathsf {S}}_{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 \( {\mathsf {S}}_{2}^{P}} \) is closed under unions, intersections, and complements. Comparing the definition with that of \( \Sigma _{{2}}^{P} \) and \( \Pi _{{2}}^{P} \), it also follows immediately that \( {\mathsf {S}}_{2}^{P}} \) is contained in \( \Sigma _{{2}}^{P}\cap \Pi _{{2}}^{P} \). This inclusion can in fact be strengthened to ZPPNP.[1]
Every language in NP also belongs to \( {\mathsf {S}}_{2}^{P}} \). 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 \( {\mathsf {S}}_{2}^{P}} \) 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 \( {\mathsf {S}}_{2}^{P}} \). These straightforward inclusions can be strengthened to show that the class \( {\mathsf {S}}_{2}^{P}} \) contains MA (by a generalization of the Sipser–Lautemann theorem) and \( \Delta _{{2}}^{P} \)(more generally, \( {\displaystyle P^{{\mathsf {S}}_{2}^{P}}={\mathsf {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 \( {\mathsf {S}}_{2}^{P}} \) is not contained in SIZE(nk) for any fixed k.
Symmetric hierarchy
As an extension, it is possible to define \( {\displaystyle {\mathsf {S}}_{2}} \) as an operator on complexity classes; then \( {\displaystyle {\mathsf {S}}_{2}P={\mathsf {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.
References
Cai, Jin-Yi (2007), " \( {\displaystyle \mathrm {S} _{2}^{p}\subseteq \mathrm {{ZPP}^{NP}} } \)" (PDF), Journal of Computer and System Sciences, 73 (1): 25–35, doi:10.1016/j.jcss.2003.07.015, MR 2279029. 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. S2CID 15331219.
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
