Content deleted Content added
→W hierarchy: Elaborating on single-tape/multi-tape, what aspects are bounded or not |
short description |
||
Line 1:
{{Short description|branch of computational complexity theory}}
In [[computer science]], '''parameterized complexity''' is a branch of [[computational complexity theory]] that focuses on classifying [[computational problems]] according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. The complexity of a problem is then measured as a [[Function (mathematics)|function]] of those parameters. This allows the classification of [[NP-hard]] problems on a finer scale than in the classical setting, where the complexity of a problem is only measured by the number of bits in the input. The first systematic work on parameterized complexity was done by {{harvtxt|Downey|Fellows|1999}}.
Under the assumption that [[P versus NP problem|P ≠ NP]], there exist many natural problems that require superpolynomial [[running time]] 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 parameter {{mvar|k}}. Hence, if {{mvar|k}} is fixed at a small value and the growth of the function over {{mvar|k}} is relatively small then such problems can still be considered "tractable" despite their traditional classification as "intractable".
| |||