Complexity Zoo:W

From Qwiki

Jump to: navigation, search

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

W[1] - WAPP - W[P] - WPP - W[SAT] - W[*] - W[t] - W*[t]


W[1]: Weighted Analogue of NP

The class of decision problems of the form (x,k) (k a parameter), that are fixed-parameter reducible to the following:

    Weighted 3SAT: Given a 3SAT formula, does it have a satisfying assignment of Hamming weight k?

A fixed-parameter reduction is a Turing reduction that takes time at most f(k)p(|x|), where f is an arbitrary function and p is a polynomial. Also, if the input is (x,k), then all Weighted 3SAT instances the algorithm queries about must have the form <x',k'> where k' is at most k.

Contains FPT.

Defined in [DF99], where the following is also shown:

  • If FPT = W[1] then NP is contained in DTIME(2o(n)).

W[1] can be generalized to W[t].

WAPP: Weak Almost-Wide PP

The class of decision problems for which there exists a #P function f, a polynomial p, and an ε > 0, such that for all inputs x,

  1. If the answer is "yes" then 2p(|x|) ≥ f(x) > (1+ε) 2p(|x|)-1.
  2. If the answer is "no" then 0 ≤ f(x) < (1-ε) 2p(|x|)-1.

Defined in [BGM02], where it is also shown that WAPP is contained in AWPP and SBP.

W[P]: Weighted Circuit Satisfiability

The class of decision problems of the form (x,k) (k a parameter), that are fixed-parameter reducible to the following problem, for some constant h:

    Weighted Circuit-SAT: Given a Boolean circuit C (with no restriction on depth), does C have a satisfying assignment of Hamming weight k?

See W[1] for the definition of fixed-parameter reducibility.

Defined in [DF99].

Contains W[SAT].

WPP: Wide 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 their difference exactly equals a function f(x) computable in polynomial time (i.e. FP).

Defined in [FFK94].

Contained in C=P ∩ coC=P, as well as AWPP.

Contains SPP and LWPP.

W[SAT]: Weighted Satisfiability

The class of decision problems of the form (x,k) (k a parameter), that are fixed-parameter reducible to the following problem, for some constant h:

    Weighted SAT: Given a Boolean formula F (with no restriction on depth), does F have a satisfying assignment of Hamming weight k?

See W[1] for the definition of fixed-parameter reducibility.

Defined in [DF99].

Contains W[t] for every t, and is contained in W[P].

W[*]: Union of W[t]'s

The union of W[t] over all t.

W[t]: Nondeterministic Fixed-Parameter Hierarchy

A generalization of W[1].

The class of decision problems of the form (x,k) (k a parameter), that are fixed-parameter reducible to the following problem, for some constant h:

    Weighted Weft-t Depth-h Circuit-SAT: Given a Boolean circuit C, with a mixture of fanin-2 and unbounded-fanin gates. The number unbounded-fanin gates along any path to the root is at most t, and the total depth (fanin-2 and unbounded-fanin) is at most h. Does C have a satisfying assignment of Hamming weight k?

See W[1] for the definition of fixed-parameter reducibility.

Defined in [DF99].

Contained in W[SAT] and in W*[t].

W*[t]: W[t] With Parameter-Dependent Depth

Same as W[t], except that now the circuit depth can depend on the parameter k rather than being constant. (The number of unbounded-fanin gates along any path to the root is still at most t.)

W*[1] = W[1] [DFT96], and W*[2] = W[2] [DF97], but the problem is open for larger t.

Retrieved from "http://qwiki.stanford.edu/wiki/Complexity_Zoo:W"
Personal tools