The Number of Satisfying Assignments of Random Regular k-SAT Formulas
The Number of Satisfying Assignments of Random Regular k-SAT Formulas
复制标题
随机正则k-SAT公式的满意分配数
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
N. Wormald
中科院分区：
文献类型：
--
作者：
A. Coja;N. Wormald
设Φ是一个随机k-SAT公式，其中每个变量恰好出现d次正和d次负。假设k足够大，并且d略低于公式以高概率变得不可满足的临界度，我们确定满足分配的数量的极限分布。
Let Φ be a random k-SAT formula in which every variable occurs precisely d times positively and d times negatively. Assuming that k is sufficiently large and that d is slightly below the critical degree where the formula becomes unsatisfiable with high probability, we determine the limiting distribution of the number of satisfying assignments.