Parameterized complexity: Difference between revisions

Revision as of 08:52, 20 July 2006

Revision as of 15:43, 26 August 2006

Line 1:

In [[computer science]], '''parameterized complexity''' is a measure of complexity of problems with multiple inputsinput parameters. It is based on the fact that several such [[NP-hard]] are [[tractable]] when one of their input parameters is fixed.

The existence of efficient, exact, and deterministic solving algorithms for [[NP-complete]] problems is considered unlikely, if inputs are not fixed; all known solving algorithms for these problems require time that is [[Exponential time|exponential]] in the total size of the inputs. However, some problems can be solved by algorithms that are exponential in the size of one input and polynomial in the size of the other inputs. Such an algorithm is called a '''fixed-parameter algorithm''', because the problem can be solved efficiently by fixing the "troublesome" input at any one value. <!-- is this correct? it somehow implies that FPT=constant input --> A problem that allows for such an algorithm is called '''fixed-parameter tractable''', and the early name of the theory of parameterized complexity was '''fixed-parameter tractability'''.