M. Cesati, The Turing Way to Parameterized Complexity, Journal of Computer and System Sciences 67 (2003) 654-685

We propose a general proof technique based on the Turing machine halting problem that allows us to establish membership results for the classes W[1], W[2], and W[P]. Using this technique, we prove that Perfect Code belongs to W[1], Steiner Tree belongs to W[2], and a-Balanced Separator, Maximal Irredundant Set, and Bounded DFA Intersection belong to W[P].

Back to the Marco Cesati's research page.