About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Random Structures and Algorithms
Paper
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. 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 ≤ double-struck E sign max F ≤ m. We prove that for random formulas with m = ⌊cn⌋ clauses: for constants c < 1, double-struck E sign max F is ⌊cn⌋ - θ(1/n); for large c, it approaches ((3/4)c + θ(√c))n; and 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.