Guided Search and a Faster Deterministic Algorithm for 3-SAT

DOI10.1007/978-3-540-78773-0_6zbMATH Open1136.68521OpenAlexW1488940485MaRDI QIDQ5458517FDOQ5458517

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

• Title not available (Why is that?)
• Chain, generalization of covering code, and deterministic algorithm for \(k\)-SAT
• An efficient algorithm for 3NF determination
• Derandomizing the HSSW algorithm for 3-SAT
• A new upper bound for \(( n , 3)\)-MAX-SAT
• An improved deterministic local search algorithm for 3-SAT

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)