Parameterized complexity: Difference between revisions

Revision as of 08:04, 27 October 2021

Revision as of 17:11, 30 October 2021

Line 1:

{{Short description|branchBranch 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 as a function of the number of bits in the input. The first systematic work on parameterized complexity was done by {{harvtxt|Downey|Fellows|1999}}.