A Kolmogorov Complexity Proof of the Lovász Local Lemma for Satisfiability.
Jochen MessnerThomas ThieraufPublished in: Electron. Colloquium Comput. Complex. (2011)
Keyphrases
- kolmogorov complexity
- inductive inference
- satisfiability problem
- decision procedures
- johnson lindenstrauss
- complexity measures
- theorem proving
- computational complexity
- np complete
- theorem prover
- phase transition
- satisfiability testing
- presburger arithmetic
- propositional logic
- first order logic
- feature vectors
- expert systems
- quantified boolean formulas
- artificial intelligence