On Local Versus Global Satisfiability
Luca Trevisan · SIAM Journal on Discrete Mathematics · 2004
We prove an extremal combinatorial result regarding the fraction of satisfiable clauses in Boolean conjunctive normal form (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.