改进的k-SAT确定性算法:链的推广与递推证明
Improved Deterministic Algorithms for $k$-SAT: Generalization of Chains and Recurrence Proof
Binbin Cui, S. Cliff Liu, Yongrui Yu
AI 速读 基于摘要
作者提出一个运行时间为1.32736^n的3-SAT确定性算法,基于分支-链框架并加入多项式时间扩展过程形成块结构,结合去随机化局部搜索与枚举归约到2-SAT。
cs.DS
查看原文摘要
We present a deterministic algorithm for 3-SAT running in $1.32736^n$ time. The algorithm is built on a branching-and-chain framework augmented with a polynomial-time expansion procedure that joins short chains through additional clauses to form bounded-size blocks, which impose stronger constraints on the assignment space. After branching, the algorithm chooses between derandomized local search guided by the block structure and enumeration of block assignments together with selected port variables, reducing the remaining formula to 2-SAT. A weighted analysis of branching, partial-assignment, and local-search costs, together with inductive bounds for chains and block interactions, establishes the running-time guarantee. The framework is self-contained and also offers guidance for practical SAT solver design by identifying useful clause-overlap structures and suggesting when to switch between local-search and reduction-based strategies.