Parameterized complexity: Difference between revisions

Revision as of 16:01, 26 August 2006

Revision as of 20:47, 29 August 2006

Line 1:

In [[computer science]], '''parameterized complexity''' is a measure of complexity of problems with multiple input parameters. ItThe istheory basedof parameterized complexity was developed onin the fact1990s thatby severalRod suchDowney [[NP-hard]]and areMichael Fellows. Their 1999 [[tractablehttp://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]] whenpresents onean ofintroduction theirto input parameters isthe fixedfield.

The theory of parameterized complexity is motivated, among other things, by the observation that there exist problems that are of exponential-time complexity (or [[NP-hard]]), 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.

Line 35 ⟶ 37:

| url=http://www.oup.com/uk/catalogue/?ci=9780198566076

}} ISBN 0-19-856607-7

[[Category:Computational complexity theory]]