Luca Trevisan.<br>
<b>On Local versus Global Satisfiability.</b><br>
Manuscript, March 1997.

<dl>

<dt> <b> Abstract </b><dd>

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.

</dl>