Advancing stochastic 3-SAT solvers by dissipating oversatisfied constraints

• 成果类型: Article
• 署名作者: Schwardt, Joachim; Budich, Jan Carl
• 署名单位: Max Planck Society; Technische Universitat Dresden
• 刊物名称: PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA
• ISSN/ISSBN: 0027-8424; 1091-6490
• DOI: 10.1073/pnas.2517297122
• 发表日期: 2025-11-18
• 页码: e2517297122
• 关键词: Boolean satisfiability; stochastic local search algorithms; NP-complete problems; LOCAL SEARCH; sat; algorithm; noise

摘要

We introduce and benchmark a stochastic local search heuristic for the Non-deterministic Polynomial Time (NP) complete satisfiability problem 3-SAT that drastically outperforms existing solvers in the notoriously difficult realm of critically hard instances. Our construction is based on the crucial observation that well established previous approaches such as WalkSAT are prone to get stuck in local minima that are distinguished from true solutions by a larger number of oversatisfied combinatorial constraints. To address this issue, the proposed algorithm dissipates oversatisfied constraints (DOC), hence coined DOCSAT, i.e. reduces their unfavorable abundance so as to render them critical. We analyze and benchmark our algorithm on a randomly generated sample of hard but satisfiable 3-SAT instances with varying problem sizes up to N = 15,000. Quite remarkably, we find that DOCSAT outperforms both WalkSAT and other well known algorithms including the complete solver Kissat, even when comparing its ability to solve the hardest quintile of the sample to the average performance of its competitors. The essence of DOCSAT may be seen as a way of harnessing statistical structure beyond the primary cost function of a combinatorial problem to avoid or escape local minima traps in stochastic local search, which opens avenues for generalization to other optimization problems.