NEW WORST-CASE UPPER BOUND FOR COUNTING EXACT SATISFIABILITY

DOI10.1142/S0129054114500270zbMath1304.68084MaRDI QIDQ2941085

Junping Zhou, Wei-hua Su, Jian-An Wang

Publication date: 21 January 2015

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

zbMATH Keywords

upper boundresolution principle\#XSATcommon literals principle

Mathematics Subject Classification ID

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

Related Items (1)

Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems

Cites Work

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

This page was built for publication: NEW WORST-CASE UPPER BOUND FOR COUNTING EXACT SATISFIABILITY