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].
Cesati, M. (2003). The Turing way to parameterized complexity. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 67(4), 654-685 [10.1016/S0022-0000(03)00073-4].
The Turing way to parameterized complexity
Cesati M.
2003-12-01
Abstract
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].File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
1-s2.0-S0022000003000734-main.pdf
accesso aperto
Descrizione: Articolo principale
Tipologia:
Versione Editoriale (PDF)
Licenza:
Creative commons
Dimensione
279.56 kB
Formato
Adobe PDF
|
279.56 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
