Polynomial Time SAT Decision for Complementation-Invariant Clause-Sets, and Sign-non-Singular Matrices

DOI10.1007/978-3-540-72788-0_30MaRDI QIDQ3612474zbMATH OpenOpenAlexFDO

Authors Oliver Kullmann

Publication date 10 March 2009

Published in Theory and Applications of Satisfiability Testing – SAT 2007 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-72788-0_30

Mathematics Subject Classification ID

Hypergraphs (05C65) Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• On the use of autarkies for satisfiability decision
• Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets
• Theory and Applications of Satisfiability Testing
• Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference.
• A simplified NP-complete satisfiability problem

Cited in

(4)

• Computing maximal autarkies with few and simple oracle queries
• Theory and Applications of Satisfiability Testing
• Present and Future of Practical SAT Solving
• Theory and Applications of Satisfiability Testing

This page was built for publication: Polynomial Time SAT Decision for Complementation-Invariant Clause-Sets, and Sign-non-Singular Matrices

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