ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > WEIGHTED EXACT CNF SATISFIABILITY:
Reports tagged with Weighted Exact CNF Satisfiability:
TR00-080 | 24th July 2000
Marco Cesati

Perfect Code is W[1]-complete

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 ... more >>>



ISSN 1433-8092 | Imprint