Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > CNF FORMULAS:
Reports tagged with CNF formulas:
TR03-050 | 16th June 2003
Daniel Král

#### Locally satisfiable formulas

A CNF formula is k-satisfiable if each k clauses of it can be satisfied
simultaneously. Let \pi_k be the largest real number such that for each
k-satisfiable formula with variables x_i, there are probabilities p_i
with the following property: If each variable x_i is chosen randomly and
independently to be ... more >>>

ISSN 1433-8092 | Imprint