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

With random inputs, certain decision decision problems undergo a "phase transition". We prove similar behavior in an optimization context.
Specifically, random 2-SAT formulas with clause/variable density less than 1 are almost always satisfiable, and those with density greater than 1 are almost always unsatisfiable; the "scaling window" is also known. We prove a similar phase structure for MAX 2-SAT: for density c<1, the expected number of clauses satisfiable is all but order 1/n; for c>1 it is all but order n; and within the same scaling window, it is all but order 1. (Our results include further detail.) For random graphs, MAX CUT behaves similarly.
For optimization problems, there is also a natural analog of the "satisfiability threshold conjecture". Although here too it remains just a conjecture, it is possible that optimization problems may prove easier to analyze than their decision analogs, and may help to elucidate them.

By: Don Coppersmith, David P. Gamarnik, Mohammad Hajiaghayi,Gregory B. Sorkin

Published in: Random Structures and Algorithms, volume 24, (no 4), pages 502-45 in 2004

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to reports@us.ibm.com .