Computational complexity of quantified Boolean formulas with fixed maximal deficiency

DOI10.1016/J.TCS.2008.07.022MaRDI QIDQ955019zbMATH OpenOpenAlexFDO

Authors Hans Kleine Büning, Xishun Zhao

Publication date 18 November 2008

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2008.07.022

zbMATH Keywords

complexitydeficiencyminimal false formulamodelquantified Boolean formula

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 5139037
• The complexity of Boolean formula minimization
• The Complexity of Boolean Formula Minimization
• scientific article; zbMATH DE number 3845566
• scientific article; zbMATH DE number 2203952
• scientific article; zbMATH DE number 1746570
• An upper bound for the circuit complexity of existentially quantified Boolean formulas
• Proof Complexity of Quantified Boolean Logic — A Survey
• On the complexity of realization of Boolean functions by formulas
• On generic complexity of the validity problem for Boolean formulas

Cites work

• (2+\(f\)(\(n\)))-SAT and its properties.
• A threshold for unsatisfiability
• An efficient algorithm for the minimal unsatisfiability problem for a subclass of CNF
• Determining computational complexity from characteristic ``phase transitions
• Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets
• Minimal False Quantified Boolean Formulas
• Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas
• Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference.
• The complexity of facets resolved
• Theory and Applications of Satisfiability Testing

Cited in

(7)

• Computing smallest MUSes of quantified Boolean formulas
• scientific article; zbMATH DE number 5139037 (Why is no real title available?)
• An extension of deficiency and minimal unsatisfiability of quantified Boolean formulas
• On the complexity of quantified linear systems
• Complexity and expressive power of second-order extended Horn logic
• Complexity of fixed-size bit-vector logics
• An upper bound for the circuit complexity of existentially quantified Boolean formulas

This page was built for publication: Computational complexity of quantified Boolean formulas with fixed maximal deficiency

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