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].
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].
The class of optimization problems such that, given an instance of length n, we can find a solution within a factor 1+ε of the optimum in time f(ε)p(n), where p is a polynomial and f is arbitrary.
Contains FPTAS and is contained in PTAS.
Defined in [CT97], where the following was also shown:
Has the same relation to FPT as RP does to P.
Defined in [AR01], where it was shown that, if the Resolution proof system is automatizable (that is, if a refutation can always be found in time polynomial in the length of the shortest refutation), then W[P] is contained in FPR.
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].