Guided Search and a Faster Deterministic Algorithm for 3-SAT

DOI10.1007/978-3-540-78773-0_6MaRDI QIDQ5458517zbMATHOpenAlexFDO

Authors D. Scheder

Publication date 15 April 2008

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

Full work available at URL https://doi.org/10.1007/978-3-540-78773-0_6

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• An improved deterministic local search algorithm for 3-SAT
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• scientific article; zbMATH DE number 1670827
• Theory and Applications of Satisfiability Testing
• scientific article; zbMATH DE number 2086385

Cites work

• scientific article; zbMATH DE number 1306877 (Why is no real title available?)
• A Computing Procedure for Quantification Theory
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• A machine program for theorem-proving
• An improved local search algorithm for 3-SAT
• Improved bound for the PPSZ/Schöning-algorithm for 3-SAT
• Solving satisfiability in less than \(2^ n\) steps

Cited in

(5)

• A new upper bound for \(( n , 3)\)-MAX-SAT
• An efficient algorithm for 3NF determination
• Chain, generalization of covering code, and deterministic algorithm for \(k\)-SAT
• An improved deterministic local search algorithm for 3-SAT
• scientific article; zbMATH DE number 2187722 (Why is no real title available?)

This page was built for publication: Guided Search and a Faster Deterministic Algorithm for 3-SAT

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