Computational Tractability: The View From Mars.
Rodney G. Downey, Michael R. Fellows, Ulrike Stege · 1999
. We describe a point of view about the parameterized computational complexity framework in the broad context of one of the central issues of theoretical computer science as a field: the problem of systematically coping with computational intractability. Those already familiar with the basic ideas of parameterized complexity will nevertheless find here something new: the emerging systematic connections between fixed-parameter tractability techniques and the design of useful heuristic algorithms, and also perhaps the philosophical maturation of the parameterized complexity program. 1. Introduction There are two different ways that one can view the theory of parameterized complexity. The easiest is as a kind of "first aid" that can sometimes be applied to problems that are NP-hard, PSPACE-hard or undecidable. That is, it can be viewed as a potential means of coping with intractability as it is classically diagnosed. The second way that one can view parameterized complexity is as a funda...