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.