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

      0 references
      0 references
      10 June 1998
      0 references
      parameterized complexity
      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

      Identifiers