Random MAX SAT, Random MAX CUT, and Their Phase Transitions

Abstract

Given a 2-SAT formula $F$ consisting of $n$ variables and $\cn$ random clauses, what is the largest number of clauses $\max F$ satisfiable by a single assignment of the variables? We bound the answer away from the trivial bounds of $(3/4)cn$ and $cn$. We prove that for $c<1$, the expected number of clauses satisfiable is $\cn-Θ(1/n)$; for large $c$, it is $((3/4)c+\Theta (\sqrt{c}))n$; for $c = 1+\eps$, it is at least $(1+\eps-O(\eps^3))n$ and at most $(1+\eps-Ω(\eps^3/\ln \eps))n$; and in the ``scaling window'' $c=1+\Theta (n^{-1/3})$, it is $cn-\Theta (1)$. In particular, just as the decision problem undergoes a phase transition, our optimization problem also undergoes a phase transition at the same critical value $c=1$. Nearly all of our results are established without reference to the analogous propositions for decision 2-SAT, and as a byproduct we reproduce many of those results, including much of what is known about the 2-SAT scaling window. We consider ``online'' versions of MAX-2-SAT, and show that for one version, the obvious greedy algorithm is optimal. 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. Finally, for random MAXCUT (the size of a maximum cut in a sparse random graph) we prove analogous results.

49 pages

References in corpus (3)

• Typical random 3-SAT formulae and the satisfiability threshold
• The Asymptotic Order of the k-SAT Threshold
• Linear Phase Transition in Random Linear Constraint Satisfaction Problem

Cited by in corpus (11)

• Critical phenomena in complex networks
• Warm-starting quantum optimization
• Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
• A Direct Mapping of Max k-SAT and High Order Parity Checks to a Chimera Graph
• MAX 2-SAT with up to 108 qubits
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples
• Evaluation of QAOA based on the approximation ratio of individual samples
• Phase transitions of extremal cuts for the configuration model
• A new upper bound for 3-SAT
• Phase Transitions of Plan Modification in Conformant Planning
• On MAXCUT in strictly supercritical random graphs, and coloring of random graphs and random tournaments