The class of decision problems of the form (x,k), k a parameter, that are solvable in time f(k)p(|x|), where f is arbitrary and p is a polynomial.
The basic class of the theory of fixed-parameter tractability, as described by Downey and Fellows [DF99].
To separate FPT and W[2], one could show there is no proof system for CNF formulae that admits proofs of size f(k)nO(1), where f is a computable function and n is the size of the formula.
Contained in FPTnu, W[1], and FPR.
Contains FPTAS [CC97], as well as FPTsu.
Contains EPTAS unless FPT = W[1] [Baz95].
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]
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:
FERT and FPERT are parameterized classes. FPERT is formally defined as the class of decision problems of the form (x, k1, k2), decidable in time f1(k1) * p(|x|) by a probabilistic Turing Machine such that
Here, f1 and f2 are arbitrary functions (f2 from the reals to <0,1/2]) and p is a polynomial.
Defined in [KW15]. Contains FERT and FPT and is contained in para-NPPP.
The class of decision problems of the form (x,k), k a parameter, that are solvable in time f(k)|x|, where f is arbitrary.
Contained in FPT
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.
Same as FPT except that the algorithm can vary with the parameter k (though its running time must always be O(p(|x|)), for a fixed polynomial p).
An alternate view is that a single algorithm can take a polynomial-length advice string, depending on k.
Defined in [DF99] (though they did not use our notation).
Same as FPT except that f has to be recursive.
Defined in [DF99] (though they did not use our notation).
The subclass of NPO problems that admit an approximation scheme in the following sense. For any ε>0, there is an algorithm that is guaranteed to find a solution whose cost is within a 1+ε factor of the optimum cost. Furthermore, the running time of the algorithm is polynomial in n (the size of the problem) and in 1/ε.
Contained in PTAS.
Defined in [ACG+99].
(Basically) the class of decision problems of the form (x,k) (k a parameter), that are solvable by a parameterized family of circuits with unbounded fanin and depth t. A uniformity condition may also be imposed.
Defined in [DF99], which should be consulted for the full definition.
Uniform G[P] (i.e. with no restriction on depth) is equal to FPT.
para-P is a less common name for FPT, but in line with other para- classes naming conventions. Its slicewise counterpart is still called XP.
The class of decision problems (x,m) (where x is an input of length |x|=n and m is an integer parameter), that are solvable by a nondeterministic (i.e. NP) machine in poly(n+m) time and O(m+log n) space simultaneously.
Defined in [Mon80].
See also FPT.
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.
If P = PSPACE, then FPT = SLICEWISE PSPACE.
Defined in [DF99].
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 solvable in time O(|x|f(k)) for some function f. The algorithm used may depend on k.
Defined in [DF99].
Contains XPuniform.
Strictly contains FPT (by diagonalization).