Parameterized complexity: Difference between revisions

Revision as of 12:34, 2 July 2010

Revision as of 12:48, 2 July 2010

Line 2:

The first systematic work on parameterized complexity was done by {{harvtxt|Downey|Fellows|1999}}.

There exist severalmany hard problems that (most[[P likelyversus NP problem|given <math>P \neq NP</math>]]) require exponential runtime 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 (small) parameter <math>k</math>. Hence, if <math>k</math> is fixed at a small value, and the growth of the function over <math>k</math> 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]] 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 size. Such an algorithm is called a [[fixed-parameter tractable]] (fpt-)algorithm, because the problem can be solved efficiently for small values of the fixed parameter.