Class Description

FPT: Fixed-Parameter Tractable

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].

Linked From

#W[t]: Sharp-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]

More about...


EPTAS: Efficient Polynomial-Time Approximation Scheme

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:

More about...


FPERT: Fixed Parameter and Error Randomized Time

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

  1. If the answer is yes, the probability of acceptance is at least 1/2 + min(f2(k2),1/|x|c)
  2. If the answer is no, the probability of acceptance is at most 1/2

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.

More about...


FPL: Fixed Parameter Linear

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

More about...


FPR: Fixed-Parameter Randomized

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.

More about...


FPTnu: Fixed-Parameter Tractable (nonuniform)

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).

More about...


FPTsu: Fixed-Parameter Tractable (strongly uniform)

Same as FPT except that f has to be recursive.

Defined in [DF99] (though they did not use our notation).

More about...


FPTAS: Fully Polynomial-Time Approximation Scheme

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].

Contained in FPT [CC97].

More about...


G[t]: Stratification of Fixed-Parameter Tractable Problems

(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.

More about...


para-P: Parameterized Polynomial time.

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.

More about...


RPP: Restricted Pseudo Polynomial-Time

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.

More about...


SLICEWISE PSPACE: Parametrized PSPACE

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].

More about...


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:

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].

More about...


XP: Fixed-Parameter Tractable for Each Parameter

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).

More about...