Faster Random k-CNF Satisfiability
Faster Random k-CNF Satisfiability
复制标题
DOI：
10.4230/lipics.icalp.2020.78
复制
发表时间：
2019-03
期刊：
影响因子：
--
通讯作者：
Andrea Lincoln;Adam B. Yedidia
中科院分区：
文献类型：
--
作者：
Andrea Lincoln;Adam B. Yedidia
我们描述了一种算法，以解决随机选择输入公式时解决布尔CNF-稳定性问题的问题。我们基于Sch {O} Ning 1999和Dantin等人的算法，并在2002年。Sch{o} ning算法通过尝试许多可能的随机分配来起作用，对于每个人来说，在该分配的附近进行了系统的搜索，满足解决方案。此问题的先前算法在时间$ o（2^{n（1- \ omega（1）/k）}）$中运行。我们的改进很简单：我们计算每个随机采样分配满足多少子句，并且仅在异常满意的子句中的任务附近进行搜索。我们表明，这样的任务更有可能接近令人满意的作业。此改进节省了$ 2^{n \ omega（\ lg^2 k）/k} $，导致整体运行时为$ o（2^{n（1- \ omega（\ lg^2 k）/ k）}）$用于随机$ k $ -sat。
We describe an algorithm to solve the problem of Boolean CNF-Satisfiability when the input formula is chosen randomly. We build upon the algorithms of Sch{o}ning 1999 and Dantsin et al.~in 2002. The Sch{o}ning algorithm works by trying many possible random assignments, and for each one searching systematically in the neighborhood of that assignment for a satisfying solution. Previous algorithms for this problem run in time $O(2^{n (1- \Omega(1)/k)})$. Our improvement is simple: we count how many clauses are satisfied by each randomly sampled assignment, and only search in the neighborhoods of assignments with abnormally many satisfied clauses. We show that assignments like these are significantly more likely to be near a satisfying assignment. This improvement saves a factor of $2^{n \Omega(\lg^2 k)/k}$, resulting in an overall runtime of $O(2^{n (1- \Omega(\lg^2 k)/k)})$ for random $k$-SAT.