A Kolmogorov complexity proof of the Lovász Local Lemma for satisfiability
A Kolmogorov complexity proof of the Lovász Local Lemma for satisfiability
复制标题
可满足性的 Lovász 局部引理的柯尔莫哥洛夫复杂度证明
DOI：
10.1016/j.tcs.2012.06.005
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Thomas Thierauf
中科院分区：
文献类型：
--
作者：
Jochen Messner;Thomas Thierauf
Lovász局部引理提供了布尔公式可满足的句法性质。Moser和Tardos提出了引理的构造性证明，即证明给出了实际构造满意分配的方法。本文基于Kolmogorov复杂性给出了该引理的另一个构造性证明。实际上，我们甚至稍微改善了他们的结果。
The Lovász Local Lemma provides a syntactic property that a Boolean formula is satisifiable. Moser and Tardos came up with a constructive proof of the lemma, i.e. the proof gives a method to actually construct a satisfying assignment. In this paper, we give another constructive proof of the lemma, based on Kolmogorov complexity. Actually, we even improve their result slightly.
登录
查看更多内容
DOI：
10.1002/rsa.3240020402
发表时间：
1991-12
期刊：
Random Struct. Algorithms
影响因子：
--
作者：
J. Beck
通讯作者：
J. Beck
更有效地对 Lovasz 局部引理进行去随机化
DOI：
--
发表时间：
2008
期刊：
arXiv.org
影响因子：
--
作者：
Robin A. Moser
通讯作者：
Robin A. Moser
Robin Moser 制作 Lovasz 局部引理算法笔记！
DOI：
--
发表时间：
2009
期刊：
影响因子：
--
作者：
J. Spencer
通讯作者：
J. Spencer
反驳邻域猜想对 SAT 的影响
影响因子：
1.1
作者：
Heidi Gebauer
通讯作者：
Heidi Gebauer
DOI：
--
发表时间：
2006
期刊：
--
影响因子：
--
作者：
Iroon Polytechniou-
通讯作者：
Iroon Polytechniou-