Difference between revisions of "Complexity Zoo:S"
(Introducing class span-L)
(→SBP: Small Bounded-Error Probability)
|(One intermediate revision by one user not shown)|
|Line 72:||Line 72:|
There exists an oracle relative to which SBP is not closed under intersection [[zooref#glm+15|[GLM+15]]].
There exists an oracle relative to which SBP is not closed under intersection [[zooref#glm+15|[GLM+15]]].
Latest revision as of 13:08, 1 July 2020
 S2P: 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 Σ2P in that the quantifiers in the second condition are reversed.
Less formally, S2P is the class of one-round games in which a prover and a disprover submit simultaneous moves to a deterministic, polynomial-time referee. In Σ2P, the prover moves first.
 S2-EXPPNP: Don't Ask
One of the caged classes of the Complexity Zoo.
SACk is the class of decision problems solvable by a family of depth-O(logkn) 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 SACk is closed under complement for every k>0.
See SAC for definition.
Not closed under complement [BCD+89].
See SAC for definition.
 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.
 SBP: Small Bounded-Error Probability
- 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 BPPpath.
- There exists an oracle relative to which SBP is not contained in Σ2P.
- SBP is closed under union.
There exists an oracle relative to which SBP is not closed under intersection [GLM+15].
The corresponding model consists of randomized protocols such that yes-inputs are accepted with probability at least α and no-inputs are accepted with probability at most α/2 where α 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/α).
The complexity measure corresponding to SBPcc is equivalent to the "corruption bound" [GW14].
 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.
 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.
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
Is called "strong" to contrast it with the ordinary Exponential Hierarchy EH.
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.
See also: PermUP.
 SFk: 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, SF2 contains both ⊕P and NP by using the counter as a witness.
Complement of Π2P.
[Uma98] has shown that the following problems are complete for Σ2P:
- 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 Σ2P-complete for DNF formulas unless Σ2P equals βPNP.)
The problem of deciding if a perfect graph is 2-clique-colorable (defined in [FMF16]) has been shown to be complete for Σ2P.
 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:
- SKChint(k(n)): Hint sense. The simulator can reproduce Arthur's view of the protocol if given a hint string of size k(n).
- SKChint(k(n)): Strict oracle sense. The simulator can reproduce Arthur's view if allowed k(n) queries to an oracle O.
- SKCavg(k(n)): Average oracle sense. For each input, the expected number of queries the simulator makes to oracle O is at most k(n).
- SKCent(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
- 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.
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.
Defined in [DF99].
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."
See also: MaxSNP.
 SO: Second-Order logic
We define second-order variable has got an arity k and represent any proposition of arity . 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.
 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.)
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[TC]: Second-Order logic with transitive closure
 SO: Iterated Second-Order logic
In Descriptive complexity we can see that :
- SO is equal to PSPACE it is also another way to write SO(TC)
- SO 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 XPuniform
 span-L: 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 NL machine.
 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.
 SPARSE: Sparse Languages
Contains the maximum matching and perfect matching problems under a pseudorandom assumption [ARZ99].
Equals the set of problems low for GapL.
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.)
Independently defined in [OH93], who called the class XP.
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]
 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.
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(2n^ε) over all ε>0. (Note that the algorithm used may vary with ε.)
 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, C0 and C1, let D0 and D1 be the distributions over their respective outputs when they're given as input a uniformly random n-bit string. We're promised that D0 and D1 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)2 > 1/3.
Another complete promise problem for SZK is Entropy Difference (ED) [GV99]. Here we're promised that either H(D0)>H(D1)+1 or H(D1)>H(D0)+1, where the distributions D0 and D1 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).
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.