New algorithms for exact satisfiability

DOI10.1016/j.tcs.2004.12.023zbMath1070.68049OpenAlexW2034758366MaRDI QIDQ1770407

Bolette Ammitzbøll Madsen, Jesper Makholm Byskov, Bjarke Skjernaa

Publication date: 6 April 2005

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

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

zbMATH Keywords

Exact solutionExponential-time algorithmBranch-and-reduce algorithmExact 3-SatisfiabilityExact Satisfiability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Related Items (12)

Partition into triangles on bounded degree graphs ⋮ NEW WORST-CASE UPPER BOUND FOR COUNTING EXACT SATISFIABILITY ⋮ New plain-exponential time classes for graph homomorphism ⋮ XSAT and NAE-SAT of linear CNF classes ⋮ Improved algorithms for the general exact satisfiability problem ⋮ On variable-weighted exact satisfiability problems ⋮ Exact algorithms for exact satisfiability and number of perfect matchings ⋮ On Some SAT-Variants over Linear Formulas ⋮ Partition into Triangles on Bounded Degree Graphs ⋮ New Plain-Exponential Time Classes for Graph Homomorphism ⋮ An algorithm for exact satisfiability analysed with the number of clauses as parameter ⋮ Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems

Cites Work

• Unnamed Item
• Algorithms for four variants of the exact satisfiability problem
• Exact 3-satisfiability is decidable in time \(O(2^{0.16254 n})\)
• Faster exact solutions for some NP-hard problems.
• An upper bound \(O(2^{0.16254n})\) for exact 3-satisfiability: a simpler proof
• A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
• The complexity of satisfiability problems

This page was built for publication: New algorithms for exact satisfiability