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.