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:
See W[1] for the definition of fixed-parameter reducibility.
Defined in [DF99].
Contained in W[SAT] and in W*[t].
Roughly, the analogue of #P for parameterized complexity. I.e. the class of parameterized counting problems that are fixed-parameter parsimonious reducible to #WSAT.Defined in [FG02], which should be consulted for the full definition. [FG02] also showed that there exist #W[1]-complete problems whose corresponding decision problems are fixed-parameter tractable (i.e. in FPT).
Complete problems for #W[1] include counting the paths or cycles of a given length in a graph and counting the chordless paths of a given length (the latter both under parsimonious and Turing reductions). Complete problems for #W[2] include the maximal chordless path problem. [CF07]
Has the same relation to W[t] as PSPACE does to NP.
Same as AW[SAT], except that the formula F can have depth at most t.
Defined in [DF99].
Contained in AW[*].
[DFT98] show that for all t, AW[t] = AW[*].
The class of decision problems of the form (x,k) (k a parameter), that are fixed-parameter reducible to the following:
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:
W[1] can be generalized to W[t].
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:
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].
The union of W[t] over all t.
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.