Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR00-080 | 24th July 2000 00:00

Perfect Code is W[1]-complete

RSS-Feed




TR00-080
Authors: Marco Cesati
Publication: 22nd September 2000 15:48
Downloads: 3390
Keywords: 


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.



ISSN 1433-8092 | Imprint