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. Given a conjunctive normal form (CNF) formula F on n variables and with m k ‐variable clauses, denote by max F the maximum number of clauses satisfiable by a single assignment of the variables. (Thus the decision problem k ‐ SAT is to determine if max F is equal to m .) With the formula F chosen at random, the expectation of max F is trivially bounded by (3/4) m ⩽ max F ⩽ m . We prove that for random formulas with m = ⌊ cn ⌋ clauses: for constants c < 1, max F is ⌊ cn ⌋ − Θ(1/ n ); for large c , it approachesand in the “window” c = 1 + Θ( n −1/3 ), it is cn − Θ(1). Our full results are more detailed, but this already shows that the optimization problem MAX 2‐ SAT undergoes a phase transition just as the 2‐ SAT decision problem does, and at the same critical value c = 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 of MAX 2‐ SAT , and show that for one version the obvious greedy algorithm is optimal; all other natural questions remain open. 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. We also prove analogous results for random MAX CUT . © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004