zbMATH — the first resource for mathematics

A spectral technique for random satisfiable 3CNF formulas. (English) Zbl 1094.68574
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). 357-363 (2003).
Summary: Let \(I\) be a random 3CNF formula generated by choosing a truth assignment \(\varphi\) for variables \(x_1,\dots,x_n\) uniformly at random and including every clause with \(i\) literals set true by \(\varphi\) with probability \(p_i\), independently. We show that for any \(0\leq\eta_2,\eta_3 \leq 1\) there is a constant \(d_{\min}\) so that for all \(d\geq d_{\min}\) a spectral algorithm similar to the graph coloring algorithm of N. Alon and N. Kahale [SIAM J. Comput. 26, 1733–1748 (1997; Zbl 0884.05042)] will find a satisfying assignment with high probability for \(p_1=d/n^2\), \(p_2=\eta_2d/n^2\), and \(p_3=\eta_3d/n^2\). Appropriately setting \(\eta_2\) and \(\eta_3\) yields natural distributions on satisfiable 3CNFs, not-all-equal-sat 3CNFs, and exactly-one-sat 3CNFs.
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.)