Misplaced Pages

S2P (complexity)

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.

In computational complexity theory, S
2 is a complexity class, intermediate between the first and second levels of the polynomial hierarchy. A language L is in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\displaystyle \mathsf S_2^P} if there exists a polynomial-time predicate P such that

  • If x ∈ L {\displaystyle x\in L} , then there exists a y such that for all z, P ( x , y , z ) = 1 {\displaystyle P(x,y,z)=1} ,
  • If x ∉ L {\displaystyle x\notin L} , then there exists a z such that for all y, P ( x , y , z ) = 0 {\displaystyle 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 S
2 is closed under unions, intersections, and complements. Comparing the definition with that of Σ 2 P {\displaystyle \Sigma _{2}^{P}} and Π 2 P {\displaystyle \Pi _{2}^{P}} , it also follows immediately that S
2 is contained in Σ 2 P ∩ Π 2 P {\displaystyle \Sigma _{2}^{P}\cap \Pi _{2}^{P}} . This inclusion can in fact be strengthened to ZPP.

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

Symmetric hierarchy

As an extension, it is possible to define S 2 {\displaystyle {\mathsf {S}}_{2}} as an operator on complexity classes; then S 2 P = S 2 P {\displaystyle {\mathsf {S}}_{2}P={\mathsf {S}}_{2}^{P}} . Iteration of S 2 {\displaystyle S_{2}} 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), " S 2 p ⊆ Z P P N P {\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.

External links

Category: