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].

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].

##### MSC:

68Q25 | Analysis of algorithms and problem complexity |

68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |

PDF
BibTeX
XML
Cite

\textit{D. Coppersmith} et al., in: Proceedings of the fourteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2003, Baltimore, MD, USA, January 12--14, 2003. New York, NY: Association for Computing Machinery; Philadelphia, PA: Society for Industrial and Applied Mathematics. 364--373 (2003; Zbl 1094.68573)