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

Publisher Website
Google Scholar
Abstract
With random inputs, certain decision problems undergo a “phase transition.” We prove similar behavior in an optimization context. Given a conjunctive normal form (CNF) formulaFonnvariables and withm k‐variable clauses, denote by maxFthe maximum number of clauses satisfiable by a single assignment of the variables. (Thus the decision problemk‐SATis to determine if maxFis equal tom.) With the formulaFchosen at random, the expectation of maxFis trivially bounded by (3/4)m⩽ 𝔼 maxF⩽m. We prove that for random formulas withm= ⌊cn⌋ clauses: for constantsc< 1, 𝔼 maxFis ⌊cn⌋ − Θ(1/n); for largec, it approaches and in the “window”c= 1 + Θ(n−1/3), it iscn− Θ(1). Our full results are more detailed, but this already shows that the optimization problemMAX2‐SATundergoes a phase transition just as the 2‐SATdecision problem does, and at the same critical valuec= 1. Most of our results are established without reference to the analogous propositions for decision 2‐SAT, and can be used to reproduce them. We consider “online” versions ofMAX2‐SAT, and show that for one version the obvious greedy algorithm is optimal; all other natural questions remain open. We can extend only our simplestMAX2‐SATresults toMAXk‐SAT, but we conjecture a “MAXk‐SATlimiting function conjecture” analogous to the folklore “satisfiability threshold conjecture,” but open even fork= 2. Neither conjecture immediately implies the other, but it is natural to further conjecture a connection between them. We also prove analogous results for randomMAX CUT. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004

This publication has 29 references indexed in Scilit: