3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
From MaRDI portal
Publication:5494972
DOI10.1109/FOCS.2011.22zbMath1292.68092OpenAlexW2120698547MaRDI QIDQ5494972
Publication date: 30 July 2014
Published in: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1109/focs.2011.22
Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20)
Related Items (16)
Local Reductions ⋮ On the optimality of exact and approximation algorithms for scheduling problems ⋮ Backdoors to Satisfaction ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ Local reduction ⋮ A satisfiability algorithm and average-case hardness for formulas over the full binary basis ⋮ Derandomizing the HSSW algorithm for 3-SAT ⋮ Towards NP-P via proof complexity and search ⋮ A combinatorial analysis for the critical clause tree ⋮ A new upper bound for \(( n , 3)\)-MAX-SAT ⋮ On the exact complexity of evaluating quantified \(k\)-\textsc{cnf} ⋮ Solving SCS for bounded length strings in fewer than \(2^n\) steps ⋮ Exploiting independent subformulas: a faster approximation scheme for \(\# k\)-SAT ⋮ Unnamed Item ⋮ An improvement of the algorithm of Hertli for the unique 3SAT problem ⋮ Unnamed Item
This page was built for publication: 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
