Luca Trevisan.
On Local versus Global Satisfiability.
Manuscript, March 1997.
Abstract
We prove an extremal combinatorial result regarding the fraction of satisfiable clauses in boolean CNF formulae enjoying a locally checkable property, thus solving a problem that has been open for several years. We then generalize the problem to arbitrary constraint satisfaction problems. We prove a tight result even in the generalized case.