Random MAX SAT, Random MAX CUT, and Their Phase Transitions
Given a 2-SAT formula F consisting of n variables and $\cn$ random clauses, what is the largest number of clauses maxF 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-Θ(1/n)$; for large c, it is ((3/4)c+Θ(c))n; for $c = 1+\eps$, it is at least $(1+\eps-O(\eps^3))n$ and at most $(1+\eps-Ω(\eps^3/\ln \eps))n$; and in the ``scaling window'' c=1+Θ(n−1/3), it is cn−Θ(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.
