Random MAX SAT, Random MAX CUT, and Their Phase Transitions

Details Random MAX SAT, Random MAX CUT, and Their Phase Transitions Random MAX SAT, Random MAX CUT, and Their Phase Transitions

2003-06-02

arxiv.org/abs/math/0306047v2

Mathematics

Combinatorics

49 pages

Scientific paper

Given a 2-SAT formula $F$ consisting of $n$ variables and $\cn$ random clauses, what is the largest number of clauses $\max F$ satisfiable by a single assignment of the variables? We bound the answer away from the trivial bounds of $(3/4)cn$ and $cn$. We prove that for $c<1$, the expected number of clauses satisfiable is $\cn-\Theta(1/n)$; for large $c$, it is $((3/4)c + \Theta(\sqrt{c}))n$; for $c = 1+\eps$, it is at least $(1+\eps-O(\eps^3))n$ and at most $(1+\eps-\Omega(\eps^3/\ln \eps))n$; and in the ``scaling window'' $c= 1+\Theta(n^{-1/3})$, it is $cn-\Theta(1)$. In particular, just as the decision problem undergoes a phase transition, our optimization problem also undergoes a phase transition at the same critical value $c=1$. Nearly all of our results are established without reference to the analogous propositions for decision 2-SAT, and as a byproduct we reproduce many of those results, including much of what is known about the 2-SAT scaling window. We consider ``online'' versions of MAX-2-SAT, and show that for one version, the obvious greedy algorithm is optimal. We can extend only our simplest MAX-2-SAT results to MAX-k-SAT, but we conjecture a ``MAX-k-SAT limiting function conjecture'' analogous to the folklore satisfiability threshold conjecture, but open even for $k=2$. Neither conjecture immediately implies the other, but it is natural to further conjecture a connection between them. Finally, for random MAXCUT (the size of a maximum cut in a sparse random graph) we prove analogous results.

Affiliated with

Also associated with

No associations

Rating

Random MAX SAT, Random MAX CUT, and Their Phase Transitions 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 Random MAX SAT, Random MAX CUT, and Their Phase Transitions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random MAX SAT, Random MAX CUT, and Their Phase Transitions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-78937