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].
Same as AW[SAT] but with 'circuit' instead of 'formula.'
Has the same relation to AW[SAT] as W[P] has to W[SAT].
Defined in [DF99].
Basically has the same relation to W[SAT] as PSPACE does to NP.
The class of decision problems of the form (x,r,k1,...,kr) (r,k1,...,kr parameters), 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 AW[*], and is contained in AW[P].
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[SAT].
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].