Complexity Zoo:S

From Qwiki

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,

1. If the answer is 'yes,' then there exists a y such that for all z, P(x,y,z) is true.
2. 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].

---

S2-EXP•PNP: 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,

1. If the answer is "yes" then f(x) > g(x).
2. 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.

---

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.

See also: PermUP.

---

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:

SF4 is contained in BP ⊕PMod_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 NP 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.

See also: PKC.

---

SL: Symmetric Logarithmic-Space

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

1. If the answer is 'yes,' one or more computation paths accept.
2. If the answer is 'no,' all paths reject.
3. 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-reduction.

SL contains L, and is contained in NL. Actually, SL = L [Rei04], but that has been discovered only at long last:

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).

The story ends with the remarkable result that SL = L (even relative to an oracle) [Rei04].

---

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. For example (see [Pap94]), the property "graph G has a Hamiltonian path" is expressible as

There exists a relation P(u,v) on vertices of G, such that P(u,u) is false, and for all distinct u,v either P(u,v) or P(v,u), and P(u,v) and P(v,w) implies P(u,w), and if P(u,w) and there does not exist a v for which P(u,v) and P(v,w), then there is an edge from u to w.

(Here the relation P(u,v) defines a total order on vertices, such that any two consecutive vertices must be adjacent.)

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.

See also: MaxSNP.

---

SO-E: Second Order Existential

The class of decision problems for which a "yes" answer is expressible by a proposition with second-order existential quantifiers followed by a first-order formula. See [Imm98] for a full definition.

SO-E = NP [Fag74].

Contains FO(poly(n)).

---

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

1. If the answer is "no," then the number of accepting computation paths exactly equals the number of rejecting paths.
2. 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, except that now the verifier can exchange only a single round of quantum messages with the two provers. The verifier may process the yes-prover's response before sending a message to the no-prover (compare with RG[1], wherein the verifier's messages must be sent to the provers in parallel).

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

SQG is contained in EXP [Gut05], as well as in QRG.

SQG trivially contains QS₂P.

---

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 a protocol, we have a BPP (i.e. probabilistic polynomial-time) verifier, Arthur, and a prover, Merlin, who has unbounded computational resources. By sending messages back and forth with Merlin, Arthur 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, Arthur has a "view" of his entire interaction with Merlin, consisting of his random coins as well as all messages sent back and forth. Then the distribution over views resulting from interaction with Merlin has to be statistically close to a distribution that Arthur could generate himself (in polynomial-time), without interacting with Merlin. (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, Arthur can pick one of the graphs (each with probability 1/2), permute its vertices randomly, send the resulting graph to Merlin, and ask, "Which graph did I start with, G or H?" If G and H are non-isomorphic, Merlin 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 Merlin always gives the correct answer, Arthur becomes convinced the graphs are not isomorphic. On the other hand, Arthur already knew which graph (G or H) he started with, so he could simulate his entire view of the interaction himself, without Merlin'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. I.e. Arthur 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. I.e. 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 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].

Zero-knowledge proofs were first studied in [GMW91], [GMR89].

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.