Content deleted Content added
m →W hierarchy: Highlighted definition of weft. |
m The use of the word "small" is misleading. Any problem can be solved efficiently for "small" (i.e., finite) inputs, by simply hardcoding the finite number of results. The point is that with FPT algorithms, the function in terms of the parameter is eaten away by the big-Oh, and thus treated as a constant. |
||
Line 4:
Under the assumption that [[P versus NP problem|P ≠ NP]], there exist many natural problems that require superpolynomial [[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 {{mvar|k}}. Hence, if {{mvar|k}} is fixed at a small value and the growth of the function over {{mvar|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 time|exponential]] (so in particular superpolynomial) in the total size of the input. However, some problems can be solved by algorithms that are exponential only in the size of a fixed parameter while polynomial in the 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
Problems in which some parameter {{mvar|k}} is fixed are called parameterized problems. A parameterized problem that allows for such an fpt-algorithm is said to be a '''fixed-parameter tractable''' problem and belongs to the class {{sans-serif|FPT}}, and the early name of the theory of parameterized complexity was '''fixed-parameter tractability'''.
| |||