Complexity Zoo:S

Back to the Main Zoo - Complexity Garden - Zoo Glossary - Zoo References

Complexity classes by letter: Symbols - A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z

Lists of related classes: Communication Complexity - Hierarchies - Nonuniform

S^≠ - S₂P - S₂E - S₂-EXP•P^NP - SAC - SAC⁰ - SAC¹ - SAPTIME - SBP - SBP^cc - SBQP - SC - SE - SEH - SelfNP - SF_k - Σ₂P - SIZE(f(n)) - SKC - SL - SLICEWISE PSPACE - SNP - SO - SO(Horn) - SO(Krom) - SO(LFP) - SO(TC) - SO[ $t(n)$ ] - SP - span-L - span-P - SPARSE - SPL - SPP - SQG - SUBEXP - symP - SZK - SZK_h

S₂P: Second Level of the Symmetric Hierarchy

The class of decision problems for which there is a polynomial-time predicate P such that, on input x,

If the answer is 'yes,' then there exists a y such that for all z, P(x,y,z) is true.
If the answer is 'no,' then there exists a z such that for all y, P(x,y,z) is false.

Note that this differs from Σ₂P in that the quantifiers in the second condition are reversed.

Less formally, S₂P is the class of one-round games in which a prover and a disprover submit simultaneous moves to a deterministic, polynomial-time referee. In Σ₂P, the disprover moves first.

Defined in [RS98], where it was also shown that S₂P contains MA and Δ₂P. Defined independently in [Can96].

Contained in ZPP^NP [Cai01].

Contains (and contrast with) O₂P. If NP is contained in P/poly then PH = S₂P (attributed to Sengupta in [Cai01]), and even is equal to O₂P [CR06].

S₂-EXPP^NP: Don't Ask

One of the caged classes of the Complexity Zoo.

Has been implicated in a collapse scandal involving AM[polylog], coNP, and EH.

SAC: Semi-Unbounded-Fanin AC

SAC^k is the class of decision problems solvable by a family of depth-O(log^kn) circuits with unbounded-fanin OR & bounded-fanin AND gates. Negations are only allowed at the input level.

A uniformity condition may also be imposed.

Defined by [BCD+89], who also showed that SAC_k is closed under complement for every k>0.

SAC⁰: Semi-Unbounded-Fanin AC⁰

See SAC for definition.

Not closed under complement [BCD+89].

SAC¹: Semi-Unbounded-Fanin AC¹

See SAC for definition.

Equals LOGCFL/poly [Ven91].

Contained in ⊕SAC¹ [GW96].

SAPTIME: Stochastic Alternating Polynomial-Time

The class of problems solvable by a polynomial-time Turing machine with three kinds of quantifiers: existential, universal, and randomized.

Defined in [Pap83], where it was also observed that SAPTIME = PSPACE.

SBP: Small Bounded-Error Probability

The class of decision problems for which the following holds. There exists a #P function f and an FP function g such that, for all inputs x,

If the answer is "yes" then f(x) > g(x).
If the answer is "no" then f(x) < g(x)/2.

Defined in [BGM02], where the following was also shown:

SBP contains MA, WAPP, and ∃BPP.
SBP is contained in AM and BPP_path.
There exists an oracle relative to which SBP is not contained in Σ₂P.
SBP is closed under union.

SBQP: Small Bounded-Error Quantum Polynomial-Time

The class of decision problems for which there exists a polynomial-time quantum algorithm that accepts with probability at least 2^−p(n) if the answer is "yes", and with probability at most 2^−p(n)−1 if the answer is "no", for some polynomial p.

Defined by Kuperberg in [Kup09], where he showed that SBQP = A₀PP.

SC: Steve's Class

(Named in honor of Stephen Cook.)

The class of decision problems solvable by a Turing machine that simultaneously uses polynomial time and polylogarithmic space.

Note that SC might be smaller than P ∩ polyL, since for the latter, it suffices to have two separate algorithms: one polynomial-time and the other polylogarithmic-space.

Deterministic context-free languages (DCFLs) can be recognized in SC [Coo79].

SC contains RL and BPL [Nis92].

SC equals DTISP(poly,polylog) by definition.

SE: Subexponentially-Solvable Search Problems

The class of FNP search problems solvable in O(2^εn) time for every ε>0.

Defined in [IPZ01], who also gave reductions showing that if any of k-SAT, k-colorability, k-set cover, clique, or vertex cover is in SE, then all of them are.

SEH: Strong Exponential Hierarchy

The union of NE, NP^NE, NP^{NP^NE}, and so on.

Is called "strong" to contrast it with the ordinary Exponential Hierarchy EH.

Note that we would get the same class if we replaced NE by NEXP.

SEH collapses to P^NE [Hem89]

There exists an oracle relative to which SEH is not contained in EH [Hem89]. EH and SEH are incomparable for all anyone knows.

SelfNP: Self-Witnessing NP

The class of languages L in NP such that the union, over all x in L, of the set of valid witnesses for x equals L itself.

Defined in [HT03], where it was shown that the closure of SelfNP under polynomial-time many-one reductions is NP.

They also show that if SelfNP = NP, then E = NE; and that SAT is contained in SelfNP.

SF_k: Width-k Bottleneck Turing Machines

The class of decision problems solvable by a k-bottleneck Turing machine. This is a machine that, after a polynomial amount of time, erases everything on the tape except for a single k-valued "safe-storage". There's also a counter recording the number of erasings, which is in effect a non-deterministic witness. For example, SF₂ contains both ⊕P and NP by using the counter as a witness.

Defined in [CF91], where it was also shown that SF₅ = PSPACE.

The complexity of SF₂, SF₃, and SF₄ was studied in [Ogi94] and [Her97]. The following result of those authors is among the caged beasts of the Complexity Zoo:

SF₄ is contained in BP ⊕P^{Mod_3P ^ ⊕P ^ Mod_3P ^ ⊕P}

(Here the BP operator means that one makes the class into a bounded-error probabilistic class, the same way one makes P into BPP and NP into AM.)

Σ₂P: NP With coNP Oracle

Complement of Π₂P.

Along with Π₂P, comprises the second level of PH, the polynomial hierarchy.

[Uma98] has shown that the following problems are complete for Σ₂P:

Minimum equivalent DNF. Given a DNF formula F and integer k, is there a DNF formula equivalent to F with k or fewer occurences of literals?
Shortest implicant. Given a formula F and integer k, is there a conjunction of k or fewer literals that implies F? (Note that this problem cannot be Σ₂P-complete for DNF formulas unless Σ₂P equals βP^NP.)

For any fixed k, there is a problem in Σ₂P ∩ Π₂P that cannot be solved by circuits of size n^k [Kan82].

SKC: Statistical Knowledge Complexity

A hierarchy of generalizations of SZK, in which Arthur is allowed to gain some information from his interaction with Merlin.

Defined in [GP91].

There are several variants (which we only describe roughly), including:

SKC_hint(k(n)): Hint sense. The simulator can reproduce Arthur's view of the protocol if given a hint string of size k(n).
SKC_hint(k(n)): Strict oracle sense. The simulator can reproduce Arthur's view if allowed k(n) queries to an oracle O.
SKC_avg(k(n)): Average oracle sense. For each input, the expected number of queries the simulator makes to oracle O is at most k(n).
SKC_ent(k(n)): Entropy sense. Defined in [ABV95]. For each input, the expectation (over Arthur's random coins) of -log(P) is at most k(n), where P is the probability that the view output by the simulator equals the view resulting from the actual protocol.

SL: Symmetric Logarithmic-Space

The class of problems solvable by a nondeterministic Turing machine in logarithmic space, such that

If the answer is 'yes,' one or more computation paths accept.
If the answer is 'no,' all paths reject.
If the machine can make a nondeterministic transition from configuration A to configuration B, then it can also transition from B to A. (This is what 'symmetric' means.)

Defined in [LP82].

The undirected s-t connectivity problem (USTCON: is there a path from vertex s to vertex t in a given undirected graph?) is complete for SL, under L-reductions.

SL contains L, and is contained in NL.

It follows from [AKL+79] that SL is contained in L/poly.

[KW93] showed that SL is contained in ⊕L, as well as Mod_kL for every prime k.

SL is also contained in DSPACE(log^3/2n) [NSW92], and indeed in DSPACE(log^4/3n) [ATW+00].

[NT95] showed that SL equals coSL, and furthermore that SL^SL = SL (that is, the symmetric logspace hierarchy collapses).

Reingold ultimately showed that SL = L [Rei04], even relative to an oracle. This subsumes many of the earlier results.

SLICEWISE PSPACE: Parametrized PSPACE

The parameterized version of PSPACE.

Same as FPT, except that now on input (x,k) (k a parameter), the space used must be f(k)p(|x|), where p is a polynomial.

If P = PSPACE, then FPT = SLICEWISE PSPACE.

Defined in [DF99].

SNP: Strict NP

[Fag74] showed that NP is precisely the class of decision problems reducible to a graph-theoretic property expressible in second-order existential logic.

Then SNP is the class of decision problems reducible to a graph-theoretic predicate with only universal quantifiers over vertices, no existential quantifiers. As an example, k-SAT (CNF satisfiability with at most k literals per clause, for k a constant) is in SNP. But general SAT is not in SNP, basically because we're not allowed to say, "There exists a literal in this clause that satisfies the clause."

Contains MMSNP.

SO: Second-Order logic

We define second-order variable has got an arity k and represent any proposition of arity $k$ . They are usually written in upper-case.

Second order logic is the set of FO formulae where we add quantification over second-order variables.

Every formuale is equivalent to a formulae in prenex normal form, where we first write quantification on variable on second order and then a FO-formulae in prenex normal form.

In Descriptive complexity we can see that SO is equal to PH, more precisely we have that formulae in prenex normal form where existantial and universal of second order alternate k times are the kth level of the polynomial hierarchy.

This means that SO with only existantial second-order quantification is equal to $\Sigma ^{1}$ which is NP, and with only universal quantification is equal to $\Pi ^{1}$ which is Co-NP.

SO(Horn): Second-order in Horn form

SO(horn) is the set of boolean queries definable with second-order formulae in normal form such that the quantifier-free part of the formula is in conjunctive normal form with at most one positive instance of a quantified relation per clause. (Atomic queries to the database don't count.)

It was shown in [Grä92] that this class is equal to P.

Those formulae can be made in prenex form where the second order is existential and the first order universal without loss of generality.

SO(Krom): Second-order in Krom form

SO(krom) is the set of boolean queries definable with second-order formulae in normal form such that the quantifier-free part of the formula is in Krom form, wich means that in every clause there is at most two literals and the first-order portion contains no existential quantifiers.

It was shown in [Grä92] that this class is equal to NL.

Those formulaes can be made in prenex form where the second order is existential and the first order universal without loss of generalities.

SO[LFP]: Second-Order logic with least fixed point

SO[LFP] is to SO what FO[LFP] is to FO. The LFP operator can now also take second-order variable as argument.

In Descriptive complexity we can see that SO[LFP] is equal to EXPTIME.

SO[TC]: Second-Order logic with transitive closure

SO[TC] is to SO what FO[TC] is to FO. The TC operator can now also take second-order variable as argument.

In Descriptive complexity we can see that : SO[TC] is equal to PSPACE.

SO[ $t(n)$ ]: Iterated Second-Order logic

SO[ $t(n)$ ] is to SO what FO[ $t(n)$ ] is to FO. But we now also have second-order quantifier in the quantifier block.

In Descriptive complexity we can see that :

SO[ $n^{O(1)}$ ] is equal to PSPACE it is also another way to write SO(TC)
SO[ $2^{n^{O(1)}}$ ] is equal to EXPTIME it is also another way to write SO(LFP)

SP: Semi-Efficient Parallel

The class of problems in P for which the best parallel algorithm (using a polynomial number of processors) is faster than the best serial algorithm by a factor of Ω(n^ε) for some ε>0.

Defined in [KRS90].

SP is also an alternate name for XP_uniform

span-P: Span Polynomial-Time

The class of functions computable as |S|, where S is the set of output values returned by the accepting paths of an NP machine.

Defined in [KST+89], where it is also shown that span-P contains #P and OptP; and that span-P = #P if and only if UP = NP.

SPARSE: Sparse Languages

The class of decision problems for which the number of 'yes' instances of size n is upper-bounded by a polynomial in n. If SPARSE intersects NPC then P = NP [Mah82].

Contains TALLY.

SPL: Stoic PL

Has the same relation to PL as SPP does to PP.

Contains the maximum matching and perfect matching problems under a pseudorandom assumption [ARZ99].

Contains UL.

Contained in C₌L and Mod_kL.

Equals the set of problems low for GapL.

SPP: Stoic PP

The class of decision problems solvable by an NP machine such that

If the answer is "no," then the number of accepting computation paths exactly equals the number of rejecting paths.
If the answer is "yes," then these numbers differ by 2.

(A technicality: If the total number of paths is even then the numbers can't differ by 1.)

Defined in [FFK94], where it was also shown that SPP is low for PP, C₌P, Mod_kP, and SPP itself. (I.e. adding SPP as an oracle does not increase the power of these classes.)

Independently defined in [OH93], who called the class XP.

Contained in LWPP, C₌P, and WPP among other classes.

Contains FewP; indeed, FewP is low for SPP, so that SPP^FewP = SPP [FFK94].

Contains the problem of deciding whether a graph has any nontrivial automorphisms [KST92].

Indeed, contains graph isomorphism [AK02].

Contains a whole gaggle of problems for solvable black-box groups: solvability testing, membership testing, subgroup testing, normality testing, order verification, nilpotetence testing, group isomorphism, and group intersection [Vin04]

[AK02] also showed that the Hidden Subgroup Problem for permutation groups, of interest in quantum computing, is in FP^SPP.

SQG: Short Quantum Games

Same as QRG(2), except that now the verifier can process the yes-prover's answer before preparing the no-prover's question.

Defined in [GW05], where it was also shown that SQG contains QIP.

SQG is contained in EXP [Gut05].

SQG is trivially contained in QRG(4) (and hence EXP).

SQG trivially contains QRG(2) (and hence PSPACE).

SQG is contained in PSPACE [GW10]. Hence SQG = QRG(2) = RG(2) = PSPACE and the addition of quantum information, combined with the ability of the verifier to process the one prover's answer before preparing the other prover's question, has no effect on the complexity of two-turn (one-round) zero-sum games.

SUBEXP: Deterministic Subexponential-Time

The intersection of DTIME(2^{n^ε}) over all ε>0. (Note that the algorithm used may vary with ε.)

symP: Alternate Name for S₂P

SZK: Statistical Zero Knowledge

The class of decision problems for which a "yes" answer can be verified by a statistical zero-knowledge proof protocol. In such an interactive proof (see IP), we have a probabilistic polynomial-time verifier, and a prover who has unbounded computational resources. By exchanging messages with the prover, the verifier must become convinced (with high probability) that the answer is "yes," without learning anything else about the problem (statistically).

What does that mean? For each choice of random coins, the verifier has a "view" of his entire interaction with prover, consisting of his random coins as well as all messages sent back and forth. Then the distribution over views resulting from interaction with the prover has to be statistically close to a distribution that the verifier could generate himself (in polynomial-time), without interacting with anyone. (Here "statistically close" means that, say, the trace distance is at most 1/10.)

The most famous example of such a protocol is for graph nonisomorphism. Given two graphs G and H, the verifier picks at random one of the graphs (each with probability 1/2), permutes its vertices randomly, sends the resulting graph to the prover, and asks, "Which graph did I start with, G or H?" If G and H are non-isomorphic, the prover can always answer correctly (since he can use exponential time), but if they're isomorphic, he can answer correctly with probability at most 1/2. Thus, if the prover always gives the correct answer, then the verifier becomes convinced the graphs are not isomorphic. On the other hand, the verifier already knew which graph (G or H) he started with, so he could simulate his entire view of the interaction himself, without the prover's help.

If that sounds like a complicated definition, well, it is. But it turns out that SZK has extremely nice properties. [Oka96] showed that:

SZK is closed under complement. E.g., a verifier can verify in zero-knowledge that two graphs are isomorphic, not only that they aren't.
We can assume without loss of generality that the whole interaction consists of a constant number of messages.
Amazingly, we can also assume without loss of generality that the protocol is public-coin. That is, the verifier (often called Arthur) doesn't need to hide any of his random bits, as he did in the graph nonisomorphism protocol above, but can just send them all to the prover (called Merlin)!
Finally, we can assume without loss of generality that the verifier (Arthur) is honest. A dishonest verifier would be one that tries to learn something about the problem (violating the zero-knowledge requirement) by deviating from the protocol.

Subsequently, [SV97] showed that SZK has a natural complete promise problem, called Statistical Difference (SD). Given two polynomial-size circuits, C₀ and C₁, let D₀ and D₁ be the distributions over their respective outputs when they're given as input a uniformly random n-bit string. We're promised that D₀ and D₁ have trace distance either at most 1/3 or at least 2/3; the problem is to decide which is the case.

Note: The constants 1/3 and 2/3 can be amplified to 2^-poly(n) and 1-2^-poly(n) respectively. But it is crucial that (2/3)² > 1/3.

Another complete promise problem for SZK is Entropy Difference (ED) [GV99]. Here we're promised that either H(D₀)>H(D₁)+1 or H(D₁)>H(D₀)+1, where the distributions D₀ and D₁ are as above, and H denotes Shannon entropy. The problem is to determine which is the case.

If any hard-on-average language is in SZK, then one-way functions exist [Ost91].

See general zero-knowledge (ZK).

Contains PZK and NISZK, and is contained in AM ∩ coAM, as well as CZK and QSZK.

There exists an oracle relative to which SZK is not in BQP [Aar02].

Contained in DQP [Aar02b].

SZK_h: SZK With Limited Help

The class of decision problems for which a "yes" answer can be verified by a statistical zero-knowledge proof protocol, and the prover and verifier both have access to a string computed by a trusted probabilistic polynomial-time third party with access to the input.

Defined in [BG03], where it was also shown that SZK_h = SZK.

Contains NISZK_h.