3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
From MaRDI portal
Publication:5494972
DOI10.1109/FOCS.2011.22zbMath1292.68092MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68W20: Randomized algorithms
Related Items
Unnamed Item, Unnamed Item, An improvement of the algorithm of Hertli for the unique 3SAT problem, 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, On the optimality of exact and approximation algorithms for scheduling problems, Local reduction, 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, Backdoors to Satisfaction, What’s Next? Future Directions in Parameterized Complexity, Local Reductions
