Improved randomized algorithms for 3-SAT

DOI10.1007/978-3-642-17517-6_9MaRDI QIDQ3060723zbMATH OpenOpenAlexFDO

Authors Kazuhisa Seto, Tadashi Takai, Suguru Tamaki, Kazuo Iwama

Publication date 9 December 2010

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-17517-6_9

zbMATH Keywords

randomized algorithms3-SATexponential-time algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• Randomized algorithms for 3-SAT
• scientific article; zbMATH DE number 2086385
• Improved bound for the PPSZ/Schöning-algorithm for 3-SAT
• An improvement of the algorithm of Hertli for the unique 3SAT problem
• Theory and Applications of Satisfiability Testing

Cited in

(12)

• Randomized algorithms for 3-SAT
• An improved local search algorithm for 3-SAT
• New methods for 3-SAT decision and worst-case analysis
• scientific article; zbMATH DE number 1113996 (Why is no real title available?)
• MaxMinMax problem and sparse equations over finite fields
• An improvement of the algorithm of Hertli for the unique 3SAT problem
• An improvement of the algorithm of Hertli for the unique 3SAT problem
• Improved agreeing-gluing algorithm
• On the exact complexity of evaluating quantified \(k\)-\textsc{cnf}
• PPSZ for general k-SAT and CSP -- making Hertli's analysis simpler and 3-SAT faster
• AI 2003: Advances in Artificial Intelligence
• scientific article; zbMATH DE number 2086385 (Why is no real title available?)

This page was built for publication: Improved randomized algorithms for 3-SAT

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