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

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