S2P (complexity)
≈ 3 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In computational complexity theory, S is a complexity class, intermediate between the first and second levels of the polynomial hierarchy. A language is in \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.
In computational complexity theory, S is a complexity class, intermediate between the first and second levels of the polynomial hierarchy. A language is in \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 S 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 S is contained in \Sigma_{2}^P \cap \Pi_{2}^P . This inclusion can in fact be strengthened to ZPP NP .
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(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 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 These straightforward inclusions can be strengthened to show that the class contains MA (by a generalization of the Sipser–Lautemann theorem) and \Delta_{2}^P (more generally, 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 . This result yields a strengthening of Kannan's theorem: it is known that S is not contained in (n k ) for any fixed k.
Symmetric hierarchy
As an extension, it is possible to define \mathsf S_2 as an operator on complexity classes; then \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.
External links
Complexity Class of the Week: S 2 P , Lance Fortnow, August 28, 2002.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1352443884 under CC BY-SA 4.0; modifications have been made.