Content deleted Content added
→FPT: “... if graph coloring parameterised by the number of colors were in FPT,...” is more accurate than “... if graph coloring were in FPT,...” |
|||
Line 27:
===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 ''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>n^k</math>.
An example is the [[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 <math>O(2^km)</math>. A [[vertex cover]] of size ''k'' in a graph of size ''m'' can be found in time <math>O(2^km)</math>, so this problem is also in FPT.
| |||