Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR97-012 | 19th March 1997 00:00

On Local versus Global Satisfiability

RSS-Feed




TR97-012
Authors: Luca Trevisan
Publication: 16th April 1997 17:31
Downloads: 2127
Keywords: 


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.



ISSN 1433-8092 | Imprint