← 研踪 PaperTrailarXiv:2611.09335 · v1
Tight Variable-Occurrence Bounds and Exponential Separations for Moser--Tardos and WalkSAT on 3-CNF
首次提交 2026-11-06 19:31
版本更新 2026-11-06 19:31
雷达观测 2026-11-09 11:19
摘要
We establish a sharp variable-occurrence threshold for polynomial expected-time convergence for the Moser--Tardos algorithm and the pure random-walk WalkSAT on 3-CNF formulas. For every formula with $m$ clauses and at most two occurrences per variable, both algorithms terminate in $O(m)$ expected updates. This occurrence bound is sharp: we construct an infinite family with at most three occurrences per variable on which both algorithms require $2^{Θ(\sqrt{m})}$ expected updates. Surprisingly, this dynamical transition occurs strictly below the classical NP-completeness threshold at variable-occurrence degree four. We further establish exponential separations between the two algorithms on satisfiable 3-CNF formulas. On one family, WalkSAT terminates in $O(m^4)$ expected flips, whereas MT requires $2^{Ω(m)}$ expected resampling steps. On another, MT terminates in $O(m)$ expected resampling steps, whereas WalkSAT requires $2^{Ω(m)}$ expected flips. These constructions exploit the different ways in which single-variable flips and simultaneous resampling propagate local violations. Our results show that the algorithms' expected running times are incomparable even up to polynomial overhead on the same inputs.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-06 19:31 · 最新观测版本
Tight Variable-Occurrence Bounds and Exponential Separations for Moser--Tardos and WalkSAT on 3-CNF
We establish a sharp variable-occurrence threshold for polynomial expected-time convergence for the Moser--Tardos algorithm and the pure random-walk WalkSAT on 3-CNF formulas. For every formula with $m$ clauses and at most two occurrences per variable, both algorithms terminate in $O(m)$ expected updates. This occurrence bound is sharp: we construct an infinite family with at most three occurrences per variable on which both algorithms require $2^{Θ(\sqrt{m})}$ expected updates. Surprisingly, this dynamical transition occurs strictly below the classical NP-completeness threshold at variable-occurrence degree four. We further establish exponential separations between the two algorithms on satisfiable 3-CNF formulas. On one family, WalkSAT terminates in $O(m^4)$ expected flips, whereas MT requires $2^{Ω(m)}$ expected resampling steps. On another, MT terminates in $O(m)$ expected resampling steps, whereas WalkSAT requires $2^{Ω(m)}$ expected flips. These constructions exploit the different ways in which single-variable flips and simultaneous resampling propagate local violations. Our results show that the algorithms' expected running times are incomparable even up to polynomial overhead on the same inputs.
查看此版本解读 →查看此版本原文 ↗