New worst-case upper bound for counting exact satisfiability

DOI10.1142/S0129054114500270MaRDI QIDQ2941085zbMATH OpenFDO

Authors Junping Zhou, Wei-hua Su, Jianan Wang

Publication date 21 January 2015

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0129054114500270

zbMATH Keywords

upper boundresolution principle\#XSATcommon literals principle

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40)

Recommendations

• New algorithms for exact satisfiability
• New upper bound for the \#3-SAT problem
• Improved algorithms for the general exact satisfiability problem
• On variable-weighted exact satisfiability problems
• The worst-case upper bound for exact 3-satisfiability with the number of clauses as the parameter

Cites work

• A tighter upper bound for random MAX \(2\)-SAT
• Algorithms for four variants of the exact satisfiability problem
• An upper bound \(O(2^{0.16254n})\) for exact 3-satisfiability: a simpler proof
• Many hard examples in exact phase transitions
• New algorithms for exact satisfiability
• On exponential time lower bound of Knapsack under backtracking
• Random constraint satisfaction: easy generation of hard (satisfiable) instances
• The complexity of computing the permanent

Cited in

(8)

• New upper bound for the \#3-SAT problem
• New upper bounds for the problem of maximal satisfiability
• Logic for Programming, Artificial Intelligence, and Reasoning
• Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems
• Counting All Solutions of Minimum Weight Exact Satisfiability
• Improved algorithms for the general exact satisfiability problem
• On variable-weighted exact satisfiability problems
• Counting for satisfiability by inverting resolution

This page was built for publication: New worst-case upper bound for counting exact satisfiability

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