Improved algorithms for the general exact satisfiability problem

DOI10.1016/J.TCS.2021.07.036MaRDI QIDQ2232607zbMATH OpenOpenAlexFDO

Authors Gordon Hoi, Frank Stephan

Publication date 6 October 2021

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

Full work available at URL https://arxiv.org/abs/2101.08637

zbMATH Keywords

measure and conquerexponential time algorithmsDPLL

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• New algorithms for exact satisfiability
• Algorithms for four variants of the exact satisfiability problem
• Logic for Programming, Artificial Intelligence, and Reasoning
• An algorithm for exact satisfiability analysed with the number of clauses as parameter
• New worst-case upper bound for counting exact satisfiability

Cites work

• A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving
• A measure \& conquer approach for the analysis of exact algorithms
• Algorithms and Computation
• Algorithms for four variants of the exact satisfiability problem
• An improved exact algorithm for the exact satisfiability problem
• Exact algorithms for exact satisfiability and number of perfect matchings
• Exact algorithms for finding minimum transversals in rank-3 hypergraphs
• Exact exponential algorithms.
• Labeled search trees and amortized analysis: Improved upper bounds for NP-hard problems
• Logic for Programming, Artificial Intelligence, and Reasoning
• New algorithms for exact satisfiability
• New methods for 3-SAT decision and worst-case analysis
• Solving SAT and SAT modulo theories, from an abstract Davis-Putnam-Logemann-Loveland procedure to \(\operatorname{DPLL}(T)\)
• The complexity of satisfiability problems
• The complexity of theorem-proving procedures

Cited in

(8)

• An algorithm for exact satisfiability analysed with the number of clauses as parameter
• Logic for Programming, Artificial Intelligence, and Reasoning
• New worst-case upper bound for counting exact satisfiability
• Algorithms for four variants of the exact satisfiability problem
• Improvements to Hybrid Incremental SAT Algorithms
• Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width
• Improving Unsatisfiability-Based Algorithms for Boolean Optimization
• New algorithms for exact satisfiability

This page was built for publication: Improved algorithms for the general exact satisfiability problem

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