Algorithms for four variants of the exact satisfiability problem

DOI10.1016/J.TCS.2004.02.035MaRDI QIDQ596105zbMATH OpenOpenAlexFDO

Authors Vilhelm Dahllöf, Peter Jonsson, Richard Beigel

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

ExactAlgorithmSAT3-satisfiabilityExact solutionComputational complexity3-SatisfiabilityCountingCounting modelsCounting problemExact satisfiabilityExponential-time algorithmSatisfiabilityX3SATXSAT

Mathematics Subject Classification ID

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

Recommendations

• New algorithms for exact satisfiability
• An improved exact algorithm for the exact satisfiability problem
• scientific article; zbMATH DE number 1113992
• Improved algorithms for the general exact satisfiability problem
• Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings
• Exact algorithms for exact satisfiability and number of perfect matchings
• scientific article; zbMATH DE number 4039349
• An exact and a randomized approach for the satisfiability problem
• Theory and Applications of Satisfiability Testing
• Algorithms for the maximum satisfiability problem

Cites work

• scientific article; zbMATH DE number 432790 (Why is no real title available?)
• scientific article; zbMATH DE number 3182201 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1305487 (Why is no real title available?)
• scientific article; zbMATH DE number 1315584 (Why is no real title available?)
• scientific article; zbMATH DE number 2086385 (Why is no real title available?)
• scientific article; zbMATH DE number 2119675 (Why is no real title available?)
• scientific article; zbMATH DE number 1405801 (Why is no real title available?)
• A Computing Procedure for Quantification Theory
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• A probabilistic algorithm for k-SAT based on limited local search and restart
• Algorithms for Sat and upper bounds on their complexity
• Algorithms for maximum independent sets
• An O(2^0.304n) Algorithm for Solving Maximum Independent Set Problem
• An improved exponential-time algorithm for k -SAT
• Counting Unlabelled Subtrees of a Tree is #P-complete
• Counting the number of solutions for instances of satisfiability
• Faster exact solutions for some NP-hard problems.
• Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
• New methods for 3-SAT decision and worst-case analysis
• Number of models and satisfiability of sets of clauses
• On the hardness of approximate reasoning
• The Complexity of Enumeration and Reliability Problems
• The Complexity of Planar Counting Problems
• The complexity of computing the permanent
• The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
• The complexity of counting in sparse, regular, and planar graphs
• Theory and Applications of Satisfiability Testing

Cited in

(17)

• An algorithm for exact satisfiability analysed with the number of clauses as parameter
• Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings
• Logic for Programming, Artificial Intelligence, and Reasoning
• New worst-case upper bound for counting exact satisfiability
• Metalevel algorithms for variant satisfiability
• Exact algorithms for exact satisfiability and number of perfect matchings
• Sort and Search: exact algorithms for generalized domination
• Exactly hittable interval graphs
• Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems
• Exact 3-satisfiability is decidable in time \(O(2^{0.16254 n})\)
• Partition into triangles on bounded degree graphs
• Counting models for 2SAT and 3SAT formulae
• Local search strikes again: PTAS for variants of geometric covering and packing
• New algorithms for exact satisfiability
• Faster exact solutions for some NP-hard problems.
• Improved algorithms for the general exact satisfiability problem
• On variable-weighted exact satisfiability problems

This page was built for publication: Algorithms for four variants of the exact satisfiability problem

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