Algorithms for four variants of the exact satisfiability problem

DOI10.1016/j.tcs.2004.02.035zbMath1068.68068OpenAlexW2089328544MaRDI QIDQ596105

Richard Beigel, Peter Jonsson, Vilhelm Dahllöf

Publication date: 10 August 2004

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

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

zbMATH Keywords

ExactAlgorithmSatisfiabilityComputational complexityExact solutionSAT3-satisfiability3-SatisfiabilityCountingCounting modelsCounting problemExact satisfiabilityExponential-time algorithmX3SATXSAT

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Partition into triangles on bounded degree graphs, NEW WORST-CASE UPPER BOUND FOR COUNTING EXACT SATISFIABILITY, Improved algorithms for the general exact satisfiability problem, On variable-weighted exact satisfiability problems, Exact algorithms for exact satisfiability and number of perfect matchings, New algorithms for exact satisfiability, Sort and Search: exact algorithms for generalized domination, Local search strikes again: PTAS for variants of geometric covering and packing, Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Number of models and satisfiability of sets of clauses
• A probabilistic algorithm for \(k\)-SAT based on limited local search and restart
• The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
• Faster exact solutions for some NP-hard problems.
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• New methods for 3-SAT decision and worst-case analysis
• Counting the number of solutions for instances of satisfiability
• Algorithms for Sat and upper bounds on their complexity
• On the hardness of approximate reasoning
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• An improved exponential-time algorithm for k -SAT
• An O(2^0.304n) Algorithm for Solving Maximum Independent Set Problem
• Algorithms for maximum independent sets
• The Complexity of Enumeration and Reliability Problems
• The Complexity of Planar Counting Problems
• Counting Unlabelled Subtrees of a Tree is #P-complete
• Theory and Applications of Satisfiability Testing
• A Computing Procedure for Quantification Theory