View source for Complexity Zoo:S

__NOTOC__
{{CZ-Letter-Menu|S}}

===== <span id="sneq" style="color:red">S<sup>≠</sup></span>: Exclusive Stochastic Languages =====
The class of languages L for which there is a real number p, and probabilistic finite automaton M, such that:
 * If x is in L, then M accepts x with some probability not exactly equal to p
 * If x is not in L, then M accepts x with probability exactly equal to p.
Defined in <ref>Abuzer Yakaryılmaz and A.C. Cem Say. Languages recognized by nondeterministic quantum finite automata. https://arxiv.org/abs/0902.2081v2</ref>, where it was shown that S<sup>≠</sup> = [[Complexity Zoo:N#nql_2|NQL]].

----

===== <span id="s2p" style="color:red">S<sub>2</sub>P</span>: 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,
<ol>
<li>If the answer is 'yes,' then there exists a y such that for all z, P(x,y,z) is true.</li>
<li>If the answer is 'no,' then there exists a z such that for all y, P(x,y,z) is false.</li>
</ol>
Note that this differs from [[#sigma2p|&#931;<sub>2</sub>P]] in that the quantifiers in the second condition are reversed.

Less formally, S<sub>2</sub>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 [[#sigma2p|&#931;<sub>2</sub>P]], the prover moves first.

Defined in [[zooref#rs98|[RS98]]], where it was also shown that S<sub>2</sub>P contains [[Complexity Zoo:M#ma|MA]] and [[Complexity Zoo:D#delta2p|&#916;<sub>2</sub>P]].  Defined independently in [[zooref#can96|[Can96]]].

Contained in [[Complexity Zoo:Z#zpp|ZPP]]<sup>[[Complexity Zoo:N#np|NP]]</sup> [[zooref#cai01|[Cai01]]]. 

Contains (and contrast with) [[Complexity Zoo:O#o2p|O<sub>2</sub>P]]. If [[Complexity Zoo:N#np|NP]] is contained in [[Complexity Zoo:P#ppoly|P/poly]] then [[Complexity Zoo:P#ph|PH]] = S<sub>2</sub>P (attributed to Sengupta in [[zooref#cai01|[Cai01]]]), and even is equal to [[Complexity Zoo:O#o2p|O<sub>2</sub>P]] [[zooref#cr06|[CR06]]].

By a padding argument to a similar result in [[#s2e|S<sub>2</sub>E]], neither S<sub>2</sub>P nor [[Complexity Zoo:O#o2p|O<sub>2</sub>P]] has any fixed poly sized circuits [[zooref#li23|[Li23]]].

----

===== <span id="s2e" style="color:red">S<sub>2</sub>E</span>: Second Level of the Symmetric Linear Exponent Hierarchy =====

Same as [[#s2p|S<sub>2</sub>P]], except that the predicate P may be exponential.

Requires maximal sized circuits (that is, size &#937;(2<sup>n</sup>/n)) [[zooref#li23|[Li23]]]. In fact, this holds for the more general class of O<sub>2</sub>E (defined analaguosly to  [[Complexity Zoo:O#o2p|O<sub>2</sub>P]]).

----
<table border="3"><tr><td>

===== <span id="s2exppnp" style="color:red">S<sub>2</sub>-EXP•P<sup>NP</sup></span>: Don't Ask =====
One of the caged classes of the Complexity Zoo.

Has been implicated in a collapse scandal involving [[Complexity Zoo:A#ampolylog|AM[polylog]]], [[Complexity Zoo:C#conp|coNP]], and [[Complexity Zoo:E#eh|EH]].
</td></tr></table>

----

===== <span id="sac" style="color:red">SAC</span>: Semi-Unbounded-Fanin [[Complexity Zoo:A#ac|AC]] =====
SAC<sup>k</sup> is the class of decision problems solvable by a family of depth-O(log<sup>k</sup>n) 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 [[zooref#bcd89|[BCD+89]]], who also showed that SAC<sub>k</sub> is closed under complement for every k&gt;0.

----

===== <span id="sac0" style="color:red">SAC<sup>0</sup></span>: Semi-Unbounded-Fanin [[Complexity Zoo:A#ac0|AC<sup>0</sup>]] =====
See [[#sac|SAC]] for definition.

Not closed under complement [[zooref#bcd89|[BCD+89]]].

----
===== <span id="sac1" style="color:red">SAC<sup>1</sup></span>: Semi-Unbounded-Fanin [[Complexity Zoo:A#ac1|AC<sup>1</sup>]] =====
See [[#sac|SAC]] for definition.

Equals [[Complexity Zoo:L#logcfl|LOGCFL]]/poly [[zooref#ven91|[Ven91]]].

Contained in [[Complexity Zoo:Symbols#paritysac1|&#8853;SAC<sup>1</sup>]] [[zooref#gw96|[GW96]]].

----
===== <span id="saptime" style="color:red">SAPTIME</span>: 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 [[zooref#pap83|[Pap83]]], where it was also observed that SAPTIME = [[Complexity Zoo:P#pspace|PSPACE]].

----
===== <span id="sbp" style="color:red">SBP</span>: Small Bounded-Error Probability =====
The class of decision problems for which the following holds.  There exists a [[Complexity Zoo:Symbols#sharpp|#P]] function f and an [[Complexity Zoo:F#fp|FP]] function g such that, for all inputs x,
<ol>
<li>If the answer is "yes" then f(x) &gt; g(x).</li>
<li>If the answer is "no" then f(x) &lt; g(x)/2.</li>
</ol>
Defined in [[zooref#bgm02|[BGM02]]], where the following was also shown:
<ul>
<li>SBP contains [[Complexity Zoo:M#ma|MA]], [[Complexity Zoo:W#wapp|WAPP]], and [[Complexity Zoo:E#existsbpp|&#8707;BPP]].</li>
<li>SBP is contained in [[Complexity Zoo:A#am|AM]] and [[Complexity Zoo:B#bpppath|BPP<sub>path</sub>]].</li>
<li>There exists an oracle relative to which SBP is not contained in [[#sigma2p|&#931;<sub>2</sub>P]].</li>
<li>SBP is closed under union.</li>
</ul>
There exists an oracle relative to which SBP is not closed under intersection [[zooref#glm+15|[GLM+15]]].

If SAT can be solved by an NP-machine with sub-exponential number of accepting paths, then SBP = [[Complexity Zoo:A#am|AM]]  {{zcite|Vol20}}.

----

===== <span id="sbpcc" style="color:red">SBP<sup>cc</sup></span>: Communication Complexity [[#sbp|SBP]] =====

The corresponding model consists of randomized protocols such that yes-inputs are accepted with probability at least &alpha; and no-inputs are accepted with probability at most &alpha;/2 where &alpha; is to be thought of as a function of n. The cost of a protocol is defined to be its communication cost plus log(1/&alpha;).

Does not contain [[Complexity Zoo:C#conpcc|coNP<sup>cc</sup>]] [[zooref#raz92|[Raz92]]] [[zooref#gw14|[GW14]]].

Contains [[Complexity Zoo:M#macc|MA<sup>cc</sup>]] but does not equal it, since SBP<sup>cc</sup> is not closed under intersection [[zooref#glm+15|[GLM+15]]].

Contained in [[Complexity Zoo:A#amcc|AM<sup>cc</sup>]] and in [[Complexity Zoo:P#postbppcc|PostBPP<sup>cc</sup>]].

The complexity measure corresponding to SBP<sup>cc</sup> is equivalent to the "corruption bound" [[zooref#gw14|[GW14]]].

----

===== <span id="sbqp" style="color:red">SBQP</span>: 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<sup>−p(n)</sup> if the answer is "yes", and with probability at most 2<sup>−p(n)−1</sup> if the answer is "no", for some polynomial p.

Defined by Kuperberg in [[zooref#kup09|[Kup09]]], where he showed that SBQP = [[Complexity Zoo:A#a0pp|A<sub>0</sub>PP]].

----

===== <span id="sc" style="color:red">SC</span>: 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 [[Complexity Zoo:P#p|P]] &#8745; [[Complexity Zoo:P#polyL|polyL]], since for the latter, it suffices to have two separate algorithms: one polynomial-time and the other polylogarithmic-space.

Deterministic context-free languages ([[Complexity Zoo:D#dcfl|DCFL]]s) can be recognized in SC [[zooref#coo79|[Coo79]]].

SC contains [[Complexity Zoo:R#rl|RL]] and [[Complexity Zoo:B#bpl|BPL]] [[zooref#nis92|[Nis92]]].

SC equals [[Complexity Zoo:D#dtisp|DTISP]](poly,polylog) by definition.

----

===== <span id="se" style="color:red">SE</span>: Subexponentially-Solvable Search Problems =====
The class of [[Complexity Zoo:F#fnp|FNP]] search problems solvable in O(2<sup>&epsilon;n</sup>) time for every &epsilon;&gt;0.

Defined in [[zooref#ipz01|[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.

----
===== <span id="seh" style="color:red">SEH</span>: Strong Exponential Hierarchy =====
The union of [[Complexity Zoo:N#ne|NE]], [[Complexity Zoo:N#np|NP]]<sup>[[Complexity Zoo:N#ne|NE]]</sup>, [[Complexity Zoo:N#np|NP]]<sup>[[Complexity Zoo:N#np|NP]]^[[Complexity Zoo:N#ne|NE]]</sup>, and so on.

Is called "strong" to contrast it with the ordinary Exponential Hierarchy [[Complexity Zoo:E#eh|EH]].

Note that we would get the same class if we replaced [[Complexity Zoo:N#ne|NE]] by [[Complexity Zoo:N#nexp|NEXP]].

SEH collapses to [[Complexity Zoo:P#p|P]]<sup>[[Complexity Zoo:N#ne|NE]]</sup> [[zooref#hem89|[Hem89]]]

There exists an oracle relative to which SEH is not contained in [[Complexity Zoo:E#eh|EH]] [[zooref#hem89|[Hem89]]].
[[Complexity Zoo:E#eh|EH]] and SEH are incomparable for all anyone knows.

----
===== <span id="selfnp" style="color:red">SelfNP</span>: Self-Witnessing [[Complexity Zoo:N#np|NP]] =====
The class of languages L in [[Complexity Zoo:N#np|NP]] such that the union, over all x in L, of the set of valid witnesses for x equals L itself.

Defined in [[zooref#ht03|[HT03]]], where it was shown that the closure of SelfNP under polynomial-time many-one reductions is [[Complexity Zoo:N#np|NP]].

They also show that if SelfNP = [[Complexity Zoo:N#np|NP]], then [[Complexity Zoo:E#e|E]] = [[Complexity Zoo:N#ne|NE]]; and that SAT is contained in SelfNP.

See also: [[Complexity Zoo:P#permup|PermUP]].

----
===== <span id="sfk" style="color:red">SF<sub>k</sub></span>: 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<sub>2</sub> contains both [[Complexity Zoo:Symbols#parityp|&#8853;P]] and [[Complexity Zoo:N#np|NP]] by using the counter as a witness.

Defined in [[zooref#cf91|[CF91]]], where it was also shown that SF<sub>5</sub> = [[Complexity Zoo:P#pspace|PSPACE]].

The complexity of SF<sub>2</sub>, SF<sub>3</sub>, and SF<sub>4</sub> was studied in [[zooref#ogi94|[Ogi94]]] and [[zooref#her97|[Her97]]].  The following result of those authors is among the caged beasts of the Complexity Zoo:
<table border="3">
<tr><td>
SF<sub>4</sub> is contained in BP [[Complexity Zoo:Symbols#parityp|&#8853;P]]<sup>[[Complexity Zoo:M#modkp|Mod_3P]] ^ [[Complexity Zoo:Symbols#parityp|&#8853;P]] ^ [[Complexity Zoo:M#modkp|Mod_3P]] ^ [[Complexity Zoo:Symbols#parityp|&#8853;P]]</sup>
</td></tr>
</table>
(Here the [[Zoo Operators#bp|BP operator]] means that one makes the class into a bounded-error probabilistic class, the same way one makes [[Complexity Zoo:P#p|P]] into [[Complexity Zoo:B#bpp|BPP]] and [[Complexity Zoo:N#np|NP]] into [[Complexity Zoo:A#am|AM]].)

----

===== <span id="sigma2p" style="color:red">&#931;<sub>2</sub>P</span>: [[Complexity Zoo:N#np|NP]] With [[Complexity Zoo:C#conp|coNP]] Oracle =====
Contains languages whose complements are in [[Complexity Zoo:P#pi2p|&#928;<sub>2</sub>P]].

Along with [[Complexity Zoo:P#pi2p|&#928;<sub>2</sub>P]], comprises the second level of [[Complexity Zoo:P#ph|PH]], the polynomial hierarchy.

[[zooref#uma98|[Uma98]]] has shown that the following problems are complete for &#931;<sub>2</sub>P:
<ul>
<li><i>Minimum equivalent DNF.</i>  Given a DNF formula F and integer k, is there a DNF formula equivalent to F with k or fewer occurences of literals?</li>
<li><i>Shortest implicant.</i>  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 &#931;<sub>2</sub>P-complete for <i>DNF</i> formulas unless &#931;<sub>2</sub>P equals [[Complexity Zoo:B#betap|&beta;P]]<sup>[[Complexity Zoo:N#np|NP]]</sup>.)</li>
</ul>

The problem of deciding if a perfect graph is 2-clique-colorable (defined in [[zooref#fmf16|[FMF16]]]) has been shown to be complete for &#931;<sub>2</sub>P.

For any fixed k, there is a problem in &#931;<sub>2</sub>P &#8745; [[Complexity Zoo:P#pi2p|&#928;<sub>2</sub>P]] that cannot be solved by circuits of size n<sup>k</sup> [[zooref#kan82|[Kan82]]].

----

===== <span id="skc" style="color:red">SKC</span>: Statistical Knowledge Complexity =====
A hierarchy of generalizations of [[#szk|SZK]], in which Arthur is allowed to gain <i>some</i> information from his interaction with Merlin.

Defined in [[zooref#gp91|[GP91]]].

There are several variants (which we only describe roughly), including:
<ul>
<li>'''SKC<sub>hint</sub>(k(n)): Hint sense.'''  The simulator can reproduce Arthur's view of the protocol if given a hint string of size k(n).</li>
<li>'''SKC<sub>hint</sub>(k(n)): Strict oracle sense.'''  The simulator can reproduce Arthur's view if allowed k(n) queries to an oracle O.</li>
<li>'''SKC<sub>avg</sub>(k(n)): Average oracle sense.'''  For each input, the <i>expected</i> number of queries the simulator makes to oracle O is at most k(n).</li>
<li>'''SKC<sub>ent</sub>(k(n)): Entropy sense.'''  Defined in [[zooref#abv95|[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.</li>
</ul>
See also: [[Complexity Zoo:P#pkc|PKC]].

----
===== <span id="sl" style="color:red">SL</span>: Symmetric Logarithmic-Space =====
The class of problems solvable by a nondeterministic Turing machine in logarithmic space, such that
<ol>
<li>If the answer is 'yes,' one or more computation paths accept.</li>
<li>If the answer is 'no,' all paths reject.</li>
<li>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.)</li>
</ol>
Defined in [[zooref#lp82|[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 [[Complexity Zoo:L#l|L]]-reductions.

SL contains [[Complexity Zoo:L#l|L]], and is contained in [[Complexity Zoo:N#nl|NL]].

It follows from [[zooref#akl79|[AKL+79]]] that SL is contained in [[Complexity Zoo:L#l/poly|L/poly]].

[[zooref#kw93|[KW93]]] showed that SL is contained in [[Complexity Zoo:Symbols#parityl|&#8853;L]], as well as [[Complexity Zoo:M#modkl|Mod<sub>k</sub>L]] for every prime k.

SL is also contained in [[Complexity Zoo:D#dspace|DSPACE]](log<sup>3/2</sup>n) [[zooref#nsw92|[NSW92]]], and indeed in [[Complexity Zoo:D#dspace|DSPACE]](log<sup>4/3</sup>n) [[zooref#atw00|[ATW+00]]].

[[zooref#nt95|[NT95]]] showed that SL equals [[Complexity Zoo:C#cosl|coSL]], and furthermore that SL<sup>SL</sup> = SL (that is, the symmetric logspace hierarchy collapses).

Reingold ultimately showed that SL = [[Complexity Zoo:L#l|L]] [[zooref#rei04|[Rei04]]], even relative to an oracle. This subsumes many of the earlier results.

----

===== <span id="slicewisepspace" style="color:red">SLICEWISE PSPACE</span>: Parametrized [[Complexity Zoo:P#pspace|PSPACE]] =====
The parameterized version of [[Complexity Zoo:P#pspace|PSPACE]].

Same as [[Complexity Zoo:F#fpt|FPT]], except that now on input (x,k) (k a parameter), the <i>space</i> used must be f(k)p(|x|), where p is a polynomial.

If [[Complexity Zoo:P#p|P]] = [[Complexity Zoo:P#pspace|PSPACE]], then [[Complexity Zoo:F#fpt|FPT]] = SLICEWISE PSPACE.

Defined in [[zooref#df99|[DF99]]].

----
===== <span id="snp" style="color:red">SNP</span>: Strict [[Complexity Zoo:N#np|NP]] =====
[[zooref#fag74|[Fag74]]] showed that [[Complexity Zoo:N#np|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 <i>only</i> 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 [[Complexity Zoo:M#mmsnp|MMSNP]].

See also: [[Complexity Zoo:M#maxsnp|MaxSNP]].

----

===== <span id="so" style="color:red">SO</span>: Second-Order logic =====
We define second-order variable has got an arity <math>k</math> and represent any proposition of arity <math>k</math>. They are usually written in upper-case.

Second order logic is the set of [[Complexity_Zoo:F#fo|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  [[zooref#imm98|Descriptive complexity]] we can see that SO is equal to [[Complexity_Zoo:P#PH|PH]], more precisely we have that formulae in prenex normal form where existential and universal of second order alternate <math>k</math> times are the <math>k</math>th level of the polynomial hierarchy. 

This means that SO with only existential second-order quantification is equal to <math>\Sigma^1</math> which is [[Complexity_Zoo:N#np|NP]], and with only universal quantification is equal to <math>\Pi^1</math> which is [[Complexity_Zoo:C#conp|Co-NP]]. 
----

===== <span id="sohorn" style="color:red">SO(Horn)</span>: Second-order in Horn form =====
SO(horn) is the set of boolean queries definable with [[Complexity_Zoo:S#so|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 [[zooref#gra92|[Grä92]]] that this class is equal to [[Complexity_Zoo:P#p|P]].

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

===== <span id="sokrom" style="color:red">SO(Krom)</span>: Second-order in Krom form =====
SO(krom) is the set of boolean queries definable with [[Complexity_Zoo:S#so|second-order]] formulae in normal form such that the quantifier-free part of the formula is in Krom form, which means that in every clause there is at most two literals and the first-order portion contains no existential quantifiers.

It was shown in [[zooref#gra92|[Grä92]]] that this class is equal to [[Complexity_Zoo:N#nl|NL]].

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

===== <span id="solfp" style="color:red">SO[LFP]</span>: Second-Order logic with least fixed point  =====
SO[LFP] is to [[Complexity_Zoo:S#so|SO]] what [[Complexity_Zoo:F#folfp|FO[LFP]]] is to [[Complexity_Zoo:F#fo|FO]]. The LFP operator can now also take second-order variable as argument.

In [[zooref#imm98|Descriptive complexity]] we can see that 
SO[LFP] is equal to [[Complexity_Zoo:E#exp|EXPTIME]].
----

===== <span id="sotc" style="color:red">SO[TC]</span>: Second-Order logic with transitive closure =====
SO[TC] is to [[Complexity_Zoo:S#so|SO]] as [[Complexity_Zoo:F#fotc|FO[TC]]] is to [[Complexity_Zoo:F#fo|FO]]. The TC operator can now also take second-order variable as argument.

In [[zooref#imm98|Descriptive complexity]] we can see that
SO[TC] is equal to [[Complexity_Zoo:P#pspace|PSPACE]].
----

===== <span id="sot" style="color:red">SO[<math>t(n)</math>]</span>: Iterated Second-Order logic =====
SO[<math>t(n)</math>] is to [[Complexity_Zoo:S#so|SO]] as [[Complexity_Zoo:F#fot|FO[<math>t(n)</math>]]] is to [[Complexity_Zoo:F#fo|FO]]. But we now also have second-order quantifier in the quantifier block.

In [[zooref#imm98|Descriptive complexity]] we can see that :
*SO[<math>n^{O(1)}</math>] is  equal to [[Complexity_Zoo:P#pspace|PSPACE]] it is also another way to write [[Complexity_Zoo:S#sotc|SO(TC)]]
*SO[<math>2^{n^{O(1)}}</math>] is equal to [[Complexity_Zoo:E#exp|EXPTIME]] it is also another way to write [[Complexity_Zoo:S#solfp|SO(LFP)]]
----

===== <span id="sp" style="color:red">SP</span>: Semi-Efficient Parallel =====
The class of problems in [[Complexity Zoo:P#p|P]] for which the best parallel algorithm (using a polynomial number of processors) is faster than the best serial algorithm by a factor of &Omega;(n<sup>&epsilon;</sup>) for some &epsilon;&gt;0.

Defined in [[zooref#krs90|[KRS90]]].

SP is also an alternate name for [[Complexity Zoo:X#xpuniform|XP<sub>uniform</sub>]]

----

===== <span id="spanl" style="color:red">span-L</span>: Span Logarithmic-Space =====
The class of functions computable as |S|, where S is the set of output values returned by the accepting paths of an [[Complexity_Zoo:N#nl|NL]] machine.

Defined in [[zooref#aj93|[AJ93]]], where it is also shown that span-L is a hard class in the sense that span-L is contained in [[Complexity Zoo:F#fp|FP]] if and only if [[Complexity_Zoo:P#p|P]] = [[Complexity Zoo:N#np|NP]].

Span-L is contained in [[Complexity Zoo:Symbols#sharpp|#P]], and if span-L = [[Complexity Zoo:Symbols#sharpp|#P]], then [[Complexity_Zoo:N#nl|NL]] = [[Complexity Zoo:N#np|NP]] [[zooref#aj93|[AJ93]]].

Span-L is contained in [[Complexity Zoo:F#fpras|FPRAS]] [[zooref#acjr21|[ACJ+21]]].

----

===== <span id="spanp" style="color:red">span-P</span>: 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 [[Complexity Zoo:N#np|NP]] machine.

Defined in [[zooref#kst89|[KST+89]]], where it is also shown that span-P contains [[Complexity Zoo:Symbols#sharpp|#P]] and [[Complexity Zoo:O#optp|OptP]]; and that span-P = [[Complexity Zoo:Symbols#sharpp|#P]] if and only if [[Complexity Zoo:U#up|UP]] = [[Complexity Zoo:N#np|NP]].

----
===== <span id="sparse" style="color:red">SPARSE</span>: 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 [[Complexity Zoo:N#npc|NPC]] then [[Complexity Zoo:P#p|P]] = [[Complexity Zoo:N#np|NP]] [[zooref#mah82|[Mah82]]].

Contains [[Complexity Zoo:T#tally|TALLY]].

----
===== <span id="spl" style="color:red">SPL</span>: Stoic [[Complexity Zoo:P#pl|PL]] =====
Has the same relation to [[Complexity Zoo:P#pl|PL]] as [[#spp|SPP]] does to [[Complexity Zoo:P#pp|PP]].

Contains the maximum matching and perfect matching problems under a pseudorandom assumption [[zooref#arz99|[ARZ99]]].

Contains [[Complexity Zoo:U#ul|UL]].

Contained in [[Complexity Zoo:C#cequalsl|C<sub>=</sub>L]] and [[Complexity Zoo:M#modkl|Mod<sub>k</sub>L]].

Equals the set of problems low for [[Complexity Zoo:G#gapl|GapL]].

----
===== <span id="spp" style="color:red">SPP</span>: Stoic [[Complexity Zoo:P#pp|PP]] =====
The class of decision problems solvable by an [[Complexity Zoo:N#np|NP]] machine such that
<ol>
<li>If the answer is "no," then the number of accepting computation paths exactly equals the number of rejecting paths.</li>
<li>If the answer is "yes," then these numbers differ by 2.</li>
</ol>
(A technicality: If the total number of paths is even then the numbers can't differ by 1.)

Defined in [[zooref#ffk94|[FFK94]]], where it was also shown that SPP is low for [[Complexity Zoo:P#pp|PP]], [[Complexity Zoo:C#cequalsp|C<sub>=</sub>P]], [[Complexity Zoo:M#modkp|Mod<sub>k</sub>P]], and SPP itself.  (I.e. adding SPP as an oracle does not increase the power of these classes.)

Independently defined in [[zooref#oh93|[OH93]]], who called the class XP.

Contained in [[Complexity Zoo:L#lwpp|LWPP]], [[Complexity Zoo:C#cequalsp|C<sub>=</sub>P]], and [[Complexity Zoo:W#wpp|WPP]] among other classes.

Contains [[Complexity Zoo:F#fewp|FewP]]; indeed, [[Complexity Zoo:F#fewp|FewP]] is low for SPP, so that SPP<sup>[[Complexity Zoo:F#fewp|FewP]]</sup> = SPP [[zooref#ffk94|[FFK94]]].

Contains the problem of deciding whether a graph has any [[Complexity_Garden#graph_automorphism|nontrivial automorphisms]] [[zooref#kst92|[KST92]]].

Indeed, contains [[Complexity_Garden#graph_isomorphism|graph isomorphism]] [[zooref#ak02|[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 [[zooref#vin04|[Vin04]]]

[[zooref#ak02|[AK02]]] also showed that the Hidden Subgroup Problem for permutation groups, of interest in quantum computing, is in [[Complexity Zoo:F#fp|FP]]<sup>SPP</sup>.

----

===== <span id="sqg" style="color:red">SQG</span>: Short Quantum Games =====
Same as [[Complexity Zoo:Q#qrg2|QRG(2)]], except that now the verifier can process the yes-prover's answer before preparing the no-prover's question.  

Defined in [[zooref#gw05|[GW05]]], where it was also shown that SQG contains [[Complexity Zoo:Q#qip|QIP]].

SQG is contained in [[Complexity Zoo:E#exp|EXP]] [[zooref#gut05|[Gut05]]].

SQG is trivially contained in [[Complexity Zoo:Q#qrgk|QRG(4)]] (and hence [[Complexity Zoo:E#exp|EXP]]).

SQG trivially contains [[Complexity Zoo:Q#qrg2|QRG(2)]] (and hence [[Complexity Zoo:P#pspace|PSPACE]]).

SQG is contained in [[Complexity Zoo:P#pspace|PSPACE]] [[zooref#gw10|[GW10]]].  Hence SQG = [[Complexity Zoo:Q#qrg2|QRG(2)]] = [[Complexity Zoo:R#rg2|RG(2)]] = [[Complexity Zoo:P#pspace|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.

----

===== <span id="subexp" style="color:red">SUBEXP</span>: Deterministic Subexponential-Time =====
The intersection of [[Complexity Zoo:D#dtime|DTIME]](2<sup>n^&epsilon;</sup>) over all &epsilon;>0.  (Note that the algorithm used may vary with &epsilon;.)

----
===== <span id="symp" style="color:red">symP</span>: Alternate Name for [[#s2p|S<sub>2</sub>P]] =====

----
===== <span id="szk" style="color:red">SZK</span>: Statistical Zero Knowledge =====
The class of decision problems for which a "yes" answer can be verified by a <i>statistical zero-knowledge proof protocol</i>.  In such an interactive proof
(see [[Complexity Zoo:I#ip|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," <i>without learning anything else about the problem</i> (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 [[Complexity_Garden#graph_isomorphism|<i>graph nonisomorphism</i>]]. 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 <i>knew</i> 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. [[zooref#oka96|[Oka96]]] showed that:
<ul>
<li>SZK is closed under complement.  E.g., a verifier can verify in zero-knowledge that two graphs <i>are</i> isomorphic, not only that they aren't.</li> 
<li>We can assume without loss of generality that the whole interaction consists of a constant number of messages.</li>
<li>Amazingly, we can also assume without loss of generality that the protocol is <i>public-coin</i>. 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)!</li>
<li>Finally, we can assume without loss of generality that the verifier (Arthur) is <i>honest</i>. A dishonest verifier would be one that tries to learn something about the problem (violating the zero-knowledge requirement) by deviating from the protocol.</li>
</ul>
Subsequently, [[zooref#sv97|[SV97]]] showed that SZK has a natural complete promise problem, called <i>Statistical Difference (SD)</i>.  Given two polynomial-size circuits, C<sub>0</sub> and C<sub>1</sub>, let D<sub>0</sub> and D<sub>1</sub> be the distributions over their respective outputs when they're given as input a uniformly random n-bit string.  We're promised that D<sub>0</sub> and D<sub>1</sub> have trace distance either at most 1/3 or at least 2/3; the problem is to decide which is the case.

<i>Note:</i> The constants 1/3 and 2/3 can be amplified to 2<sup>-poly(n)</sup> and 1-2<sup>-poly(n)</sup> respectively.  But it is crucial that (2/3)<sup>2</sup> &gt; 1/3.

Another complete promise problem for SZK is <i>Entropy Difference (ED)</i> [[zooref#gv99|[GV99]]].  Here we're promised that either H(D<sub>0</sub>)&gt;H(D<sub>1</sub>)+1 or H(D<sub>1</sub>)&gt;H(D<sub>0</sub>)+1, where the distributions D<sub>0</sub> and D<sub>1</sub> 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 [[zooref#ost91|[Ost91]]].


See general zero-knowledge ([[Complexity Zoo:Z#zk|ZK]]).

Contains [[Complexity Zoo:P#pzk|PZK]] and [[Complexity Zoo:N#niszk|NISZK]], and is contained in [[Complexity Zoo:A#am|AM]] &#8745; [[Complexity Zoo:C#coam|coAM]], as well as [[Complexity Zoo:C#czk|CZK]] and [[Complexity Zoo:Q#qszk|QSZK]].

There exists an oracle relative to which SZK is not in [[Complexity Zoo:B#bqp|BQP]] [[zooref#aar02|[Aar02]]].

Contained in [[Complexity Zoo:D#dqp|DQP]] [[zooref#aar02b|[Aar02b]]].

----

===== <span id="szkh" style="color:red">SZK<sub>h</sub></span>: [[#szk|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 [[zooref#bg03|[BG03]]], where it was also shown that SZK<sub>h</sub> = [[#szk|SZK]].

Contains [[Complexity Zoo:N#niszkh|NISZK<sub>h</sub>]].