S2P (complexity)


In computational complexity theory, S is a complexity class, intermediate between the first and second levels of the polynomial hierarchy. A language is in if there exists a polynomial-time predicate P such that
  • If, then there exists a y such that for all z,,
  • If, then there exists a z such that for all y,,
where size of y and z must be polynomial of x.

Relationship to other complexity classes

It is immediate from the definition that S is closed under unions, intersections, and complements. Comparing the definition with that of and, it also follows immediately that S is contained in. This inclusion can in fact be strengthened to ZPPNP.
Every language in NP also belongs to For by definition, a language L is in NP, if and only if there exists a polynomial-time verifier V, 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 predicate P for the same language that ignores z and otherwise behaves the same as V. By the same token, co-NP belongs to These straightforward inclusions can be strengthened to show that the class contains MA and .

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. This result yields a strengthening of Kannan's theorem: it is known that S is not contained in for any fixed k.

Symmetric hierarchy

As an extension, it is possible to define as an operator on complexity classes; then. Iteration of operator yields a "symmetric hierarchy"; the union of the classes produced in this way is equal to the Polynomial hierarchy.