A Kolmogorov complexity proof of the Lovász Local Lemma for satisfiability.
Jochen MessnerThomas ThieraufPublished in: Theor. Comput. Sci. (2012)
Keyphrases
- kolmogorov complexity
- inductive inference
- decision procedures
- satisfiability problem
- theorem proving
- propositional logic
- presburger arithmetic
- phase transition
- complexity measures
- machine learning
- linear logic
- artificial intelligence
- np complete
- reasoning problems
- supervised learning
- feature extraction
- data sets
- terminological reasoning
- johnson lindenstrauss