3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General

DOI10.1109/FOCS.2011.22MaRDI QIDQ5494972zbMATH OpenOpenAlexFDO

Authors Timon Hertli

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

Mathematics Subject Classification ID

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

Cited in

(16)

• Towards NP-P via proof complexity and search
• What's next? Future directions in parameterized complexity
• scientific article; zbMATH DE number 7561744 (Why is no real title available?)
• Local reduction
• Backdoors to satisfaction
• A satisfiability algorithm and average-case hardness for formulas over the full binary basis
• An improvement of the algorithm of Hertli for the unique 3SAT problem
• 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}
• A satisfiability algorithm for \(\mathrm{AC}^0\)
• PPSZ for general \(k\)-SAT and CSP -- making Hertli's analysis simpler and 3-SAT faster
• On the optimality of exact and approximation algorithms for scheduling problems
• Solving SCS for bounded length strings in fewer than \(2^n\) steps
• Exploiting independent subformulas: a faster approximation scheme for \(\# k\)-SAT
• Local reductions

This page was built for publication: 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General

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