Content deleted Content added
Astenosfear (talk | contribs) See also: parameterized approximation |
→FPT: Separate discussion of FPL (and its examples) into its own paragraph for clarity. |
||
Line 21:
=== FPT ===
FPT contains the ''fixed parameter tractable'' problems, which are those that can be solved in time <math>f(k) \cdot {|x|}^{O(1)}</math> for some computable function {{mvar|f}}. Typically, this function is thought of as single exponential, such as <math>2^{O(k)}</math>, but the definition admits functions that grow even faster. 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 <math>f(n,k)</math>, such as <math>k^n</math>.
The class '''FPL''' (fixed parameter linear) is the class of problems solvable in time <math>f(k) \cdot |x|</math> for some computable function {{mvar|f}}.<ref>{{harvtxt|Grohe|1999}}</ref> FPL is thus a subclass of FPT. An example is the [[Boolean satisfiability]] problem, parameterised by the number of variables. A given formula of size {{mvar|m}} with {{mvar|k}} variables can be checked by brute force in time <math>O(2^km)</math>. A [[vertex cover]] of size {{mvar|k}} in a graph of order {{mvar|n}} can be found in time <math>O(2^kn)</math>, so the vertex cover problem is also in
An example of a problem that is thought not to be in FPT is [[graph coloring]] parameterised by the number of colors. It is known that 3-coloring is [[NP-hard]], and an algorithm for graph {{mvar|k}}-colouring in time <math>f(k)n^{O(1)}</math> for <math>k=3</math> would run in polynomial time in the size of the input. Thus, if graph coloring parameterised by the number of colors were in FPT, then [[P versus NP problem|P = NP]].
|