Parameterized complexity (Q4393480)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1161563
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Parameterized complexity |
scientific article; zbMATH DE number 1161563 |
Statements
10 June 1998
0 references
parameterized complexity
0 references
0.7820895910263062
0 references
0.7616385221481323
0 references
0.7609374523162842
0 references
Parameterized complexity (English)
0 references
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''?
0 references