Exploiting partial knowledge of satisfying assignments

DOI10.1016/j.dam.2005.10.019zbMath1185.68832OpenAlexW2008475242MaRDI QIDQ2643304

Kazuo Iwama, Suguru Tamaki

Publication date: 23 August 2007

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2005.10.019

zbMATH Keywords

probabilistic algorithmNP-complete problemCNF satisfiability

Mathematics Subject Classification ID

Searching and sorting (68P10) Nonnumerical algorithms (68W05)

Uses Software

• Walksat
• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Solving satisfiability in less than \(2^ n\) steps
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• New methods for 3-SAT decision and worst-case analysis
• An improved exponential-time algorithm for k -SAT
• Parallelizing local search for CNF satisfiability using vectorization and PVM
• The complexity of theorem-proving procedures