Parameterized complexity: Difference between revisions

Revision as of 10:11, 20 January 2010

Revision as of 11:52, 20 January 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]] in two or more parameters of the input. This way, parameterized complexity achieves to classify [[NP-hard]] problems 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.

In [[computer science]], '''parameterized complexity''' is a measure of complexity of problems with multiple input parameters. The theory of parameterized complexity was developed in the 1990s by Rod Downey and [[Michael Fellows]]. Their 1999 [http://www.springer.com/east/home?SGWID=5-102-22-1519914-0&referer=www.springer.de%2Fcgi-bin%2Fsearch_book.pl%3Fisbn%3D0-387-94883-X&SHORTCUT=www.springer.com/sgw/cda/frontpage/0,11855,5-0-22-1519914-0,00.html monograph] presents an introduction to the field.

The first systematic work on parameterized complexity was done by {{harvtxt|Downey|Fellows|1999}}.

The theory of parameterized complexity is motivated, among other things, by the observation that thereThere exist several hard problems that (most likely) require exponential runtime 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 in a (small) parameter k. Hence, if k is fixed at a small value, such problems can still be considered 'tractable' despite their traditional classification as 'intractable'.

The existence of efficient, exact, and deterministic solving algorithms for [[NP-complete]], or otherwise [[NP-hard]], problems is considered unlikely, if input parameters are not fixed; all known solving algorithms for these problems require time that is [[Exponential time|exponential]] in the total size of the input. However, some problems can be solved by algorithms that are exponential only in the size of a fixed parameter while polynomial in the size of the input size. Such an algorithm is called a [[fixed-parameter tractable]] (fpt-)algorithm, because the problem can be solved efficiently for small values of the fixed parameter.