Derandomizing the HSSW algorithm for 3-SAT

DOI10.1007/978-3-642-22685-4_1zbMATH Open1277.68097arXiv1102.3766OpenAlexW1965847460MaRDI QIDQ378221FDOQ378221

Authors: Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto 

Publication date: 11 November 2013

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

Abstract: We present a (full) derandomization of HSSW algorithm for 3-SAT, proposed by Hofmeister, Sch"oning, Schuler, and Watanabe in [STACS'02]. Thereby, we obtain an O(1.3303^n)-time deterministic algorithm for 3-SAT, which is currently fastest.

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

Recommendations

• A randomized algorithm for 3-SAT
• Randomized algorithms for 3-SAT
• Improved randomized algorithms for 3-SAT
• Theory and Applications of Satisfiability Testing
• Hard random 3-SAT problems and the Davis-Putnam procedure
• An algorithm for random signed 3-SAT with intervals
• On Random 3-sat
• scientific article; zbMATH DE number 1445295

zbMATH Keywords

derandomizationdeterministic algorithm3-SAT

Mathematics Subject Classification ID

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

Cites Work

• Undirected connectivity in log-space
• Improved randomized algorithms for 3-SAT
• Derandomizing Approximation Algorithms Based on Semidefinite Programming
• Solving satisfiability in less than \(2^ n\) steps
• A full derandomization of Schöning's \(k\)-\textsc{SAT} algorithm
• 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• Improving PPSZ for 3-SAT using critical variables
• Improved bound for the PPSZ/Schöning-algorithm for 3-SAT
• Title not available (Why is that?)
• Theory and Applications of Satisfiability Testing
• Deterministic algorithms for the Lovász local lemma
• Guided Search and a Faster Deterministic Algorithm for 3-SAT
• Title not available (Why is that?)
• An improved deterministic local search algorithm for 3-SAT

Cited In (6)

• Chain, generalization of covering code, and deterministic algorithm for \(k\)-SAT
• New worst-case upper bound for counting exact satisfiability
• Local reduction
• A satisfiability algorithm and average-case hardness for formulas over the full binary basis
• An inverse design method for non-uniform flow inlet with a given shock wave
• Exploiting independent subformulas: a faster approximation scheme for \(\# k\)-SAT

This page was built for publication: Derandomizing the HSSW algorithm for 3-SAT

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