我们给出一个关于变量出现次数的阈值，使得 Moser–Tardos（MT）算法和纯随机游走 WalkSAT 在 3‑CNF 公式上能够在多项式期望时间内收敛。具体而言，若一个包含 $m$ 条子句的公式中每个变量最多出现两次，则两种算法的期望更新次数均为 $O(m)$。该界限是严格的：我们构造了一族每个变量最多出现三次的公式，使得两算法的期望更新次数达到 $2^{\Theta(\sqrt{m})}$。令人惊讶的是，这一动力学转变出现在经典的 NP 完全性阈值（变量出现次数为四）以下。进一步地，我们展示了在可满足的 3‑CNF 上两算法之间的指数级分离。对于第一族公式，WalkSAT 的期望翻转次数为 $O(m^4)$，而 MT 需要 $2^{\Omega(m)}$ 次重新抽样；对于第二族公式，MT 的期望抽样次数为 $O(m)$，而 WalkSAT 需要 $2^{\Omega(m)}$ 次翻转。这些构造利用了单变量翻转与同步重新抽样在传播局部冲突时的不同机制，表明在相同输入上，两算法的期望运行时间即使允许多项式因子也不可比较。\n\n点评：本文精准定位了变量出现次数对 MT 与 WalkSAT 效率的影响，并通过构造性例子揭示了两者在相同实例上可能出现的指数级性能差距，为理解局部搜索与抽样算法的本质差异提供了新视角。