zbMATH — the first resource for mathematics

Parameterized complexity. (English) Zbl 0914.68076
Texts and Monographs in Computer Science. Berlin: Springer. 620 p. (1998).
The book contains Downey and Fellows’ argument against the claim that computational complexity is a mathematical pedantry, by and large irrelevant to modern science. They introduce a new way to look at difficult problems (NP-complete, in the jargon) which allows them to prove (surprisingly) that some of these problems admit good algorithms for data sets of any size provided that some parameter is small enough. This is how parameterized complexity enters the game: it has generated a very good book and an interesting subject. Does it support the claim that “computational complexity is serving the community”?

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science