Computer Science – Computational Complexity
Scientific paper
2011-06-16
Computer Science
Computational Complexity
Accepted for publication in Computer Science Review [with some additional corrections]
Scientific paper
One approach to confronting computational hardness is to try to understand the contribution of various parameters to the running time of algorithms and the complexity of computational tasks. Almost no computational tasks in real life are specified by their size alone. It is not hard to imagine that some parameters contribute more intractability than others and it seems reasonable to develop a theory of computational complexity which seeks to exploit this fact. Such a theory should be able to address the needs of practicioners in algorithmics. The last twenty years have seen the development of such a theory. This theory has a large number of successes in terms of a rich collection of algorithmic techniques both practical and theoretical, and a fine-grained intractability theory. Whilst the theory has been widely used in a number of areas of applications including computational biology, linguistics, VLSI design, learning theory and many others, knowledge of the area is highly varied. We hope that this article will show both the basic theory and point at the wide array of techniques available. Naturally the treatment is condensed, and the reader who wants more should go to the texts, Downey and Fellows, Flum and Grohe, Niedermeier, and the upcoming undergraduate text Downey and Fellows.
Downey Rodney G.
Thilikos Dimitrios M.
No associations
LandOfFree
Confronting Intractability via Parameters does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Confronting Intractability via Parameters, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Confronting Intractability via Parameters will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-189595