On the Maximum Satisfiability of Random Formulas
| dc.creator | Achlioptas, Dimitris | |
| dc.creator | Naor, Assaf | |
| dc.creator | Peres, Yuval | |
| dc.date | 2003-05-10 | |
| dc.date.accessioned | 2026-07-07T04:57:54Z | |
| dc.date.available | 2026-07-07T04:57:54Z | |
| dc.description | Maximum satisfiability is a canonical NP-hard optimization problem that appears empirically hard for random instances. Let us say that a Conjunctive normal form (CNF) formula consisting of $k$-clauses is $p$-satisfiable if there exists a truth assignment satisfying $1-2^{-k}+p 2^{-k}$ of all clauses (observe that every $k$-CNF is 0-satisfiable). Also, let $F_k(n,m)$ denote a random $k$-CNF on $n$ variables formed by selecting uniformly and independently $m$ out of all possible $k$-clauses. It is easy to prove that for every $k>1$ and every $p$ in $(0,1]$, there is $R_k(p)$ such that if $r >R_k(p)$, then the probability that $F_k(n,rn)$ is $p$-satisfiable tends to 0 as $n$ tends to infinity. We prove that there exists a sequence $δ_k \to 0$ such that if $r <(1-δ_k) R_k(p)$ then the probability that $F_k(n,rn)$is $p$-satisfiable tends to 1 as $n$ tends to infinity. The sequence $δ_k$ tends to 0 exponentially fast in $k$. | |
| dc.identifier | https://arxiv.org/abs/math/0305151 | |
| dc.identifier | http://arxiv.org/abs/math/0305151 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/67425 | |
| dc.subject | Probability | |
| dc.subject | Combinatorics | |
| dc.title | On the Maximum Satisfiability of Random Formulas | |
| dc.type | text |