A Kolmogorov complexity proof of the Lovasz Local Lemma for satisfiability

被引：1

作者：

Messner, Jochen ^{[1
]}

Thierauf, Thomas ^{[1
]}

机构：

[1] Aalen Univ, D-73430 Aalen, Germany

来源：

THEORETICAL COMPUTER SCIENCE | 2012年 / 461卷

关键词：

Lovasz Local Lemma; Satisfiability; Kolmogorov complexity;

D O I：

10.1016/j.tcs.2012.06.005

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The Lovasz 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. (c) 2012 Elsevier B.V. All rights reserved.

引用

页码：55 / 64

页数：10

共 21 条

[1] A PARALLEL ALGORITHMIC VERSION OF THE LOCAL LEMMA [J].

ALON, N .

RANDOM STRUCTURES & ALGORITHMS, 1991, 2 (04) :367-378

[2]

Alon Noga, 1992, The Probabilistic Method

[3]

[Anonymous], 1989, Kolmogorov Complexity and Its Applications

[4]

[Anonymous], 1994, FDN COMPUTER SCI

[5] AN ALGORITHMIC APPROACH TO THE LOVASZ LOCAL LEMMA .1. [J].

BECK, J .

RANDOM STRUCTURES & ALGORITHMS, 1991, 2 (04) :343-365

[6]

Calude C.S., 2002, INFORM RANDOMNESS, V2nd

[7] LOPSIDED LOVASZ LOCAL LEMMA AND LATIN TRANSVERSALS [J].

ERDOS, P ;

SPENCER, J .

DISCRETE APPLIED MATHEMATICS, 1991, 30 (2-3) :151-154

[8]

Erdos P., 1975, C MATH SOC J BOLYAI, V10, P609

[9]

FORTNOW L., 2009, KOLMOGOROV COMPLEXIT

[10]

Gebauer H, 2011, PROCEEDINGS OF THE TWENTY-SECOND ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P664

← 1 2 3 →