Parameterized complexity: Difference between revisions

Revision as of 09:19, 14 June 2010

Revision as of 12:34, 2 July 2010

Line 1:

'''Parameterized complexity''' is a branch of [[computational complexity theory]] in [[computer science]] that focuses on classifying [[computational problems]] according to their inherent difficulty with respect to ''multiple'' parameters of the input. In parameterized complexity, the complexity of a problem is measured as a [[Function (mathematics)|function]] in two or more parameters of the input. This way, through parameterized complexity achieves to classify, [[NP-hard]] problems can be classified on a finer scale than this is possible 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}}.