The first systematic work on parameterized complexity was done by Downey & Fellows (1999).
Under the assumption that P ≠ NP, there exist many natural problems that require super-polynomial running time when complexity is measured in terms of the input size only but that are computable in a time that is polynomial in the input size and exponential or worse in a parameter k. Hence, if k is fixed at a small value and the growth of the function over k is relatively small then such problems can still be considered "tractable" despite their traditional classification as "intractable".
The existence of efficient, exact, and deterministic solving algorithms for NP-complete, or otherwise NP-hard, problems is considered unlikely, if input parameters are not fixed; all known solving algorithms for these problems require time that is exponential (so in particular super-polynomial) in the total size of the input.
Such an algorithm is called a fixed-parameter tractable (FPT) algorithm, because the problem can be solved efficiently (i.e., in polynomial time) for constant values of the fixed parameter.
A parameterized problem that allows for such an FPT algorithm is said to be a fixed-parameter tractable problem and belongs to the class FPT, and the early name of the theory of parameterized complexity was fixed-parameter tractability.
Many problems have the following form: given an object x and a nonnegative integer k, does x have some property that depends on k?
In many applications, for example when modelling error correction, one can assume the parameter to be "small" compared to the total input size.
Then it is challenging to find an algorithm that is exponential only in k, and not in the input size.
This concept is formalized as follows: For example, there is an algorithm that solves the vertex cover problem in
time,[1] where n is the number of vertices and k is the size of the vertex cover.
This means that vertex cover is fixed-parameter tractable with the size of the solution as the parameter.
FPT contains the fixed parameter tractable problems, which are those that can be solved in time
This is essential for a large part of the early history of this class.
The crucial part of the definition is to exclude functions of the form
An example is the Boolean satisfiability problem, parameterised by the number of variables.
A given formula of size m with k variables can be checked by brute force in time
A vertex cover of size k in a graph of order n can be found in time
FPT is closed under a parameterised notion of reductions called fpt-reductions.
Moreover, it contains all optimisation problems in NP that allow an efficient polynomial-time approximation scheme (EPTAS).
The weft is the largest number of logical units with fan-in greater than two on any path from an input to the output.
The total number of logical units on the paths (known as depth) must be limited by a constant that holds for all instances of the problem.
Many natural computational problems occupy the lower levels, W[1] and W[2].
Flum & Grohe (2006) It is known that FPT is contained in W[P], and the inclusion is believed to be strict.
However, resolving this issue would imply a solution to the P versus NP problem.
Other connections to unparameterised computational complexity are that FPT equals W[P] if and only if circuit satisfiability can be decided in time
, or if and only if there is a computable, nondecreasing, unbounded function f such that all languages recognised by a nondeterministic polynomial-time Turing machine using
nondeterministic choices are in P. W[P] can be loosely thought of as the class of problems where we have a set S of n items, and we want to find a subset
We can encode a choice as a list of k integers, stored in binary.
for some computable function f. These problems are called slicewise polynomial, in the sense that each "slice" of fixed k has a polynomial algorithm, although possibly with a different exponent for each k. Compare this with FPT, which merely allows a different constant prefactor for each value of k. XP contains FPT, and it is known that this containment is strict by diagonalization.
para-NP is the class of parameterized problems that can be solved by a nondeterministic algorithm in time