Improving PPSZ for 3-SAT using critical variables

DOI10.4230/LIPICS.STACS.2011.237MaRDI QIDQ3113688zbMATH OpenFDO

Authors Timon Hertli, Robin A. Moser, D. Scheder

Publication date 23 January 2012

Full work available at URL https://arxiv.org/abs/1009.4830, http://subs.emis.de/LIPIcs/frontdoor_9b56.html

zbMATH Keywords

3-SAT4-SATCNF formulaexponential timerandomizedSATsatisfiability

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20) Analysis of algorithms (68W40)

Recommendations

• Breaking the PPSZ barrier for unique 3-SAT
• 3-SAT faster and simpler -- unique-SAT bounds for PPSZ hold in general
• Improved bound for the PPSZ/Schöning-algorithm for 3-SAT
• A randomized algorithm for 3-SAT
• PPSZ for general \(k\)-SAT -- making Hertli's analysis simpler and 3-SAT faster

Cited in

(5)

• Towards NP-P via proof complexity and search
• scientific article; zbMATH DE number 1848397 (Why is no real title available?)
• Walksat Stalls Well Below Satisfiability
• PPSZ for general k-SAT and CSP -- making Hertli's analysis simpler and 3-SAT faster
• Algorithms for the diverse-k-SAT problem: the geometry of satisfying assignments

This page was built for publication: Improving PPSZ for 3-SAT using critical variables

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