Content deleted Content added
Rewrite intro (it was vague and inaccurate, seeming to assume P != NP) |
wikify |
||
Line 1:
In [[computer science]], '''fixed-parameter algorithms''' are an approach to attacking [[NP-hard]] problems with multiple inputs. It is believed to be difficult to find efficient, exact, deterministic solutions to these problems; all known solutions require time that is [[Exponential time|exponential]] in the total size of the inputs. However, it may be possible to find an algorithm which is exponential in the size of only one input and polynomial in the size of the other inputs. Such an algorithm is called a fixed-parameter algorithm, because if we fix the single troublesome input at any one value, the problem can be solved efficiently.
In particular, many problems have the following general 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.
| |||