Computational complexity of quantified Boolean formulas with fixed maximal deficiency

DOI10.1016/j.tcs.2008.07.022zbMath1152.68022OpenAlexW2085904272MaRDI QIDQ955019

Hans Kleine Büning, Zhao, Xishun

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

complexitymodeldeficiencyquantified Boolean formulaminimal false formula

Mathematics Subject Classification ID

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

Related Items (1)

Complexity and expressive power of second‐order extended Horn logic

Cites Work

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

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