Applications of minimal unsatisfiable formulas to polynomially reduction for formulas

MaRDI QIDQ5473177zbMATH OpenFDO

Authors Daoyun Xu

Publication date 19 June 2006

zbMATH Keywords

construction of formulaminimal unsatisfiable formulaNP-completenesspolynomially reductionSAT-problem

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Two tractable subclasses of minimal unsatisfiable formulas
• Computing unsatisfiable \(k\)-SAT instances with few occurrences per variable
• scientific article; zbMATH DE number 2201270
• An efficient algorithm for the minimal unsatisfiability problem for a subclass of CNF
• Minimally unsatisfiable CNF formulas

Cited in

(8)

• On the size of minimal unsatisfiable formulas
• The complexity of homomorphisms and renamings for minimal unsatisfiable formulas
• Minimally unsatisfiable CNF formulas
• scientific article; zbMATH DE number 7561759 (Why is no real title available?)
• scientific article; zbMATH DE number 2201270 (Why is no real title available?)
• Computing unsatisfiable \(k\)-SAT instances with few occurrences per variable
• The complexity of variable minimal formulas
• A new 3-CNF transformation by parallel-serial graphs

This page was built for publication: Applications of minimal unsatisfiable formulas to polynomially reduction for formulas

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5473177)