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

摘要

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 ¾[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.