zbMATH — the first resource for mathematics

Random MAX SAT, random MAX CUT, and their phase transitions. (English) Zbl 1094.68573
Proceedings of the fourteenth annual ACM-SIAM symposium on discrete algorithms, Baltimore, MD, USA, January 12–14, 2003. New York, NY: Association for Computing Machinery; Philadelphia, PA: Society for Industrial and Applied Mathematics (ISBN 0-89871-538-5/pbk). 364-373 (2003).
Summary: 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\pm\Theta(n^{-1/3})\). We prove a slmilar phase structure for MAX 2-SAT: for density \(c<1\), the expected number of clauses satisfiable is \(\lfloor cn\rfloor-\Theta(1/n)\); within the scaling window it is \(\lfloor cn\rfloor-\Theta(1)\); and for \(c>1\), it is \(\frac 34\lfloor cn\rfloor+\Theta (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.
For the entire collection see [Zbl 1006.00017].

68Q25 Analysis of algorithms and problem complexity
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)