Random MAX SAT, random MAX CUT, and their phase transitions

Abstract

With random inputs, certain 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, those with density greater than 1 are almost always unsatisfiable, and the "scaling window" is in the density range 1 ± Θ(n-1/3). We prove a similar phase structure for MAX 2-SAT: for density c < 1, the expected number of clauses satisfiable is [cn] - Θ(1/n); within the scaling window it is ⌊cn⌋ - Θ(1); and for c > 1, it is 3/4⌊cn⌋ + Θ(n). (Our results include further detail.) For random graphs, a maximization version of the giant-component question behaves quite differently from 2-SAT, but 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.