Derandomizing the HSSW algorithm for 3-SAT

DOI10.1007/s00453-012-9741-4zbMath1277.68097arXiv1102.3766OpenAlexW1965847460MaRDI QIDQ378221

Masaki Yamamoto, Kazuhisa Makino, Suguru Tamaki

Publication date: 11 November 2013

Published in: Algorithmica, Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1102.3766

zbMATH Keywords

derandomizationdeterministic algorithm3-SAT

Mathematics Subject Classification ID

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

Related Items

Local reduction, A satisfiability algorithm and average-case hardness for formulas over the full binary basis, NEW WORST-CASE UPPER BOUND FOR COUNTING EXACT SATISFIABILITY, Exploiting independent subformulas: a faster approximation scheme for \(\# k\)-SAT, Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT, An inverse design method for non-uniform flow inlet with a given shock wave

Cites Work

• An improved deterministic local search algorithm for 3-SAT
• Solving satisfiability in less than \(2^ n\) steps
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• Improved Randomized Algorithms for 3-SAT
• Undirected connectivity in log-space
• Derandomizing Approximation Algorithms Based on Semidefinite Programming
• Theory and Applications of Satisfiability Testing
• A full derandomization of schöning's k-SAT algorithm
• Guided Search and a Faster Deterministic Algorithm for 3-SAT
• 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item