Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT

DOI10.4230/LIPIcs.ICALP.2018.88zbMath1499.68382arXiv1804.07901OpenAlexW2963145758MaRDI QIDQ5002768

Sixue Liu

Publication date: 28 July 2021

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

zbMATH Keywords

local searchsatisfiabilityderandomization

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational aspects of satisfiability (68R07)

Related Items

Further improvements for SAT in terms of formula length ⋮ Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms ⋮ A fast algorithm for SAT in terms of formula length

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Derandomizing the HSSW algorithm for 3-SAT
• 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.
• New methods for 3-SAT decision and worst-case analysis
• An improved exponential-time algorithm for k -SAT
• 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
• A machine program for theorem-proving
• Theory and Applications of Satisfiability Testing

This page was built for publication: Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT