On the Maximum Satisfiability of Random Formulas

Details On the Maximum Satisfiability of Random Formulas On the Maximum Satisfiability of Random Formulas

2003-05-10

arxiv.org/abs/math/0305151v1

Mathematics

Probability

Scientific paper

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 $\delta_k \to 0$ such that if $r <(1-\delta_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 $\delta_k$ tends to 0 exponentially fast in $k$.

Affiliated with

Also associated with

No associations

Rating

On the Maximum Satisfiability of Random Formulas does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Maximum Satisfiability of Random Formulas, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Maximum Satisfiability of Random Formulas will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-155086