Derandomizing the HSSW algorithm for 3-SAT
From MaRDI portal
Publication:378221
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
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Randomized algorithms (68W20)
Related Items (6)
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
This page was built for publication: Derandomizing the HSSW algorithm for 3-SAT