In [[computer science]], '''fixed-parameter algorithms''' are an approach to attacking [[NP-hard]] problems with multiple inputs. WhenIt tryingis believed to solvebe thesedifficult problemsto exactlyfind andefficient, deterministicallyexact, onedeterministic hassolutions to dealthese withproblems; all known solutions require time that is exponential runningin times;the [[computationaltotal complexitysize theory]]of indicatesthe thisinputs. However, it may be possible to find an algorithm which is [[Complexityexponential classesin Pthe size of only one input and NP|inevitable]]polynomial in the size of the other inputs. ParameterizedSuch complexityan theoryalgorithm acceptsis thesecalled exponentiala runningfixed-parameter timesalgorithm, butbecause claimsif thatwe notfix allthe "intractable"single algorithmstroublesome areinput equal,at andany someone mightvalue, eventhe beproblem feasiblecan forbe practicalsolved applicationsefficiently.
TheIn mainparticular, idea is to consider ''parameters''. Manymany 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.
In this way, parameterized complexity can be seen as ''two-dimensional'' complexity theory. This concept is formalized as follows:
