Bereiche | Tage | Auswahl | Suche | Aktualisierungen | Downloads | Hilfe
DY: Fachverband Dynamik und Statistische Physik
DY 47: Statistical Physics: General I
DY 47.7: Vortrag
Donnerstag, 12. März 2026, 11:15–11:30, ZEU/0114
Advancing Stochastic 3-SAT Solvers by Dissipating Oversatisfied Constraints — •Joachim Schwardt1,2 and Jan Budich2,1 — 1Max Planck Institute for the Physics of Complex Systems — 2Institute of Theoretical Physics at TU Dresden
We introduce and benchmark a stochastic local search heuristic for the 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, coined DOCSAT, dissipates oversatisfied constraints (DOC), 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 = 15000. Quite remarkably, we find that DOCSAT outperforms both WalkSAT and other well known algorithms including the complete solver Kissat. 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.
Keywords: Boolean satisfiability; stochastic local search algorithms; NP-complete combinatorial problems