We show that the parameterized problem Perfect Code belongs to W[1]. This result closes an old open question, because it was often conjectured that Perfect Code could be a natural problem having complexity degree intermediate between W[1] and W[2]. This result also shows W[1]-membership of the parameterized problem Weighted Exact CNF Satisfiability. © 2002 Elsevier Science B.V. All rights reserved.
Cesati, M. (2002). Perfect Code is W[1]-complete. INFORMATION PROCESSING LETTERS, 81(3), 163-168 [10.1016/S0020-0190(01)00207-1].
Perfect Code is W[1]-complete
Cesati M.
2002-02-14
Abstract
We show that the parameterized problem Perfect Code belongs to W[1]. This result closes an old open question, because it was often conjectured that Perfect Code could be a natural problem having complexity degree intermediate between W[1] and W[2]. This result also shows W[1]-membership of the parameterized problem Weighted Exact CNF Satisfiability. © 2002 Elsevier Science B.V. All rights reserved.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
s0020-0190(01)00207-1.pdf
solo utenti autorizzati
Descrizione: Articolo principale
Tipologia:
Versione Editoriale (PDF)
Licenza:
Copyright dell'editore
Dimensione
75.1 kB
Formato
Adobe PDF
|
75.1 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
