Class Description

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

Linked From

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

More about...