Content deleted Content added
No edit summary |
No edit summary |
||
Line 1:
In [[computer science]], '''parameterized complexity''' is a measure of complexity of problems with multiple inputs. It is based on the fact that several such [[NP-hard]] are [[tractable]] when one of their input 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
Many problems have the following form: given an object <math>x</math> and a nonnegative integer <math>k</math>, does <math>x</math> have some property that depends on <math>k</math>? For instance, for the [[vertex cover problem]], the parameter can be the number of vertices in the cover. In many applications, for example when modelling error correction, one can assume the parameter to be "small" compared to the total input size. Then it is interesting to see whether we can find an algorithm which is exponential ''only'' in <math>k</math>, and not in the input size.
|