The threshold for SDP-refutation of random regular NAE-3SAT
The threshold for SDP-refutation of random regular NAE-3SAT
复制标题
DOI：
10.1137/1.9781611975482.140
复制
发表时间：
2018-04
期刊：
影响因子：
--
通讯作者：
Y. Deshpande;A. Montanari;R. O'Donnell;T. Schramm;S. Sen
中科院分区：
文献类型：
--
作者：
Y. Deshpande;A. Montanari;R. O'Donnell;T. Schramm;S. Sen
与它的表亲3SAT不同，NAE-3SAT（不全等于3SAT）问题具有这样的性质：当约束密度是一个大常数（具有高概率）时，谱/SDP算法可以有效地反驳随机实例。但是，这些方法是否在“可满足性阈值”之上立即工作，或者仍然存在一系列约束密度，对于这些约束密度，随机NAE-3SAT实例是不可满足的，但很难反驳？我们表明，后者的情况下占上风，至少在随机定期的情况下，基于SDP的反驳。更准确地说，而NAE-3SAT的随机$d$-正则实例一旦$d \geq 8$就很容易被证明是不可满足的（whp），我们建立了以下关于有效反驳的尖锐阈值结果：如果$d 13.5$那么即使是最基本的谱算法也会反驳可满足性~（whp）。
Unlike its cousin 3SAT, the NAE-3SAT (not-all-equal-3SAT) problem has the property that spectral/SDP algorithms can efficiently refute random instances when the constraint density is a large constant (with high probability). But do these methods work immediately above the "satisfiability threshold", or is there still a range of constraint densities for which random NAE-3SAT instances are unsatisfiable but hard to refute? We show that the latter situation prevails, at least in the context of random regular instances and SDP-based refutation. More precisely, whereas a random $d$-regular instance of NAE-3SAT is easily shown to be unsatisfiable (whp) once $d \geq 8$, we establish the following sharp threshold result regarding efficient refutation: If $d 13.5$ then even the most basic spectral algorithm refutes satisfiability~(whp).