A Kolmogorov complexity proof of the Lovász local lemma for satisfiability

DOI10.1016/J.TCS.2012.06.005MaRDI QIDQ690463zbMATH OpenOpenAlexWikidataFDO

Authors Jochen Messner, Thomas Thierauf

Publication date 27 November 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2012.06.005

zbMATH Keywords

Kolmogorov complexityLovász local lemmasatisfiability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Combinatorics in computer science (68R05)

Recommendations

• A Kolmogorov complexity proof of the Lovász local lemma for satisfiability
• A constructive proof of the Lovász local lemma
• Deterministic algorithms for the Lovász local lemma
• Deterministic algorithms for the Lovász local lemma
• A constructive proof of the general Lovász local lemma

Cites work

• A constructive proof of the general Lovász local lemma
• A constructive proof of the Lovász local lemma
• A parallel algorithmic version of the local lemma
• Algorithmics
• An algorithmic approach to the Lovász local lemma. I
• An introduction to Kolmogorov complexity and its applications
• Asymptotic lower bounds for Ramsey functions
• Disproof of the Neighborhood Conjecture with Implications to SAT
• scientific article; zbMATH DE number 5764785 (Why is no real title available?)
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• scientific article; zbMATH DE number 1911266 (Why is no real title available?)
• Hypergraph colouring and the Lovász local lemma
• Lopsided Lovász Local lemma and Latin transversals
• On a problem of Spencer
• The local lemma is tight for SAT
• The Lovász Local Lemma and Satisfiability

Cited in

(4)

• Probabilistic constructions of computable objects and a computable version of Lovász local lemma
• A Kolmogorov complexity proof of the Lovász local lemma for satisfiability
• The Lovász Local Lemma and Satisfiability
• A constructive proof of the Lovász local lemma

This page was built for publication: A Kolmogorov complexity proof of the Lovász local lemma for satisfiability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q690463)