## Abstract

Maximum satisfiability is a canonical NP-complete problem that appears empirically hard for random instances. At the same time, it is rapidly becoming a canonical problem for statistical physics. In both of these realms, evaluating new ideas relies crucially on knowing the maximum number of clauses one can typically satisfy in a random k-CNF formula. In this paper we give asymptotically tight estimates for this quantity. Let us say that a k-CNF formula is p-satisfiable if there exists a truth assignment satisfying 1-2^{-k} +p2^{-k} fraction of all clauses (every k-CNF is 0-satisfiable). Let F_{k}(n, m) denote a random k-CNF formula on n variables formed by selecting uniformly, independently and with replacement m out of all (2n)^{k} possible k-clauses. Finally, let τ(p) = 2^{k}ln 2/(p + (1 - p) ln(1 - p)). It is easy to prove that for every k ≥ 2 and p ∈ (0, 1), if r ≥ τ (p) then the probability that F_{k}(n, m = rn) is p-satisfiable tends to 0 as n tends to infinity. We prove that there exists a sequence δ_{k} → 0 such that if r ≤ (1 - δ_{k})τ(p) then the probability that F_{k}(n, m = rn) is p-satisfiable tends to 1 as n tends to infinity. The sequence δ_{k} tends to 0 exponentially fast in k. Indeed, even for moderate values of k, e.g. k = 10, our result gives very tight bounds for the fraction of satisfiable clauses in a random k-CNF. In particular, for k > 2 it improves upon all previously known such bound.

Original language | English (US) |
---|---|

Pages (from-to) | 362-370 |

Number of pages | 9 |

Journal | Annual Symposium on Foundations of Computer Science - Proceedings |

State | Published - 2003 |

Externally published | Yes |

Event | Proceedings: 44th Annual IEEE Symposium on Foundations of Computer Science - FOCS 2003 - Cambridge, MA, United States Duration: Oct 11 2003 → Oct 14 2003 |

## All Science Journal Classification (ASJC) codes

- Hardware and Architecture