The Satisfiability Threshold for k-XORSAT
The Satisfiability Threshold for k-XORSAT
复制标题
k-XORSAT 的可满足性阈值
DOI：
10.1017/s0963548315000097
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
G. Sorkin
中科院分区：
文献类型：
--
作者：
B. Pittel;G. Sorkin
我们考虑“无约束”随机k-XORSAT，这是一个均匀随机系统的m线性非齐次方程在$\mathbb{F}$2超过n个变量，每个方程包含k <$3个变量，也考虑一个“约束”模型，其中每个变量出现在至少两个方程。Dubois和Mandler证明了m/n = 1是约束3-XORSAT可满足性的一个尖锐阈值，并通过分析随机3-一致超图的2-核，将这一结果推广到寻找无约束3-XORSAT的阈值.我们发现，m/n = 1仍然是一个尖锐的阈值，满足约束k-XORSAT的每一个k <$3，我们使用标准的结果2-核心的随机k-一致超图扩展这个结果，找到无约束k-XORSAT的阈值。对于约束k-XORSAT，我们缩小了相变窗口，表明m-n → −∞意味着几乎确定可满足性，而m-n → +∞意味着几乎确定不可满足性。
We consider ‘unconstrained’ random k-XORSAT, which is a uniformly random system of m linear non-homogeneous equations in $\mathbb{F}$ 2 over n variables, each equation containing k ⩾ 3 variables, and also consider a ‘constrained’ model where every variable appears in at least two equations. Dubois and Mandler proved that m/n = 1 is a sharp threshold for satisfiability of constrained 3-XORSAT, and analysed the 2-core of a random 3-uniform hypergraph to extend this result to find the threshold for unconstrained 3-XORSAT. We show that m/n = 1 remains a sharp threshold for satisfiability of constrained k-XORSAT for every k ⩾ 3, and we use standard results on the 2-core of a random k-uniform hypergraph to extend this result to find the threshold for unconstrained k-XORSAT. For constrained k-XORSAT we narrow the phase transition window, showing that m − n → −∞ implies almost-sure satisfiability, while m − n → +∞ implies almost-sure unsatisfiability.