An extension of deficiency and minimal unsatisfiability of quantified Boolean formulas

MaRDI QIDQ3506043zbMATH OpenFDO

Authors Hans Kleine Büning, Xishun Zhao

Publication date 11 June 2008

zbMATH Keywords

cohesiondeficiencyminimal falsityminimal unsatisfiabilityQBF

Mathematics Subject Classification ID

Classical propositional logic (03B05) Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Minimal False Quantified Boolean Formulas
• Computational complexity of quantified Boolean formulas with fixed maximal deficiency
• Extension and equivalence problems for clause minimal formulae
• Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference.
• Polynomial time algorithms for computing a representation for minimal unsatisfiable formulas with fixed deficiency.

Cited in

(3)

• Extension and equivalence problems for clause minimal formulae
• scientific article; zbMATH DE number 8117 (Why is no real title available?)
• Minimal False Quantified Boolean Formulas

This page was built for publication: An extension of deficiency and minimal unsatisfiability of quantified Boolean formulas

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