The Turing way to parameterized complexity

摘要

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 α-Balanced Separator, Maximal Irredundant Set, and Bounded DFA Intersection belong to W[P].