×

Proof of the satisfiability conjecture for large \(k\). (English) Zbl 1509.60169

In this major paper, the authors derive a sharp threshold for the random \(k\)-sat problem, for the parameter \(k\) chosen large enough. They identify the threshold separating the satisfiable and the unsatisfiable regimes, and prove there is a sharp transition. In the proof they develop and apply a refined moment method, and justify the 1-RSB (one-step Replica-Symmetry-Breaking) answer which was predicted by nonrigorous physics methods originating in spin-glass theory. They reduce the problem to analysing a tree recurrence problem. The authors have spent a lot of effort in making the paper accessible and reasonably self-contained, providing earlier results, both rigorous and nonrigorous, and giving intuition and background. It makes the paper long (and a long time in finalising in view of the time between submission and publication), but it appears as an impressive accomplishment.

MSC:

60K35 Interacting random processes; statistical mechanics type models; percolation theory
82B44 Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Achlioptas, D.; Coja-Oghlan, A., Algorithmic barriers from phase transitions. Proc. 49th FOCS, IEEE, 793-802 (2008) · doi:10.1109/FOCS.2008.11
[2] Auffinger, Antonio; Chen, Wei-Kuo, The {P}arisi formula has a unique minimizer, Comm. Math. Phys.. Communications in Mathematical Physics, 335, 1429-1444 (2015) · Zbl 1320.82033 · doi:10.1007/s00220-014-2254-z
[3] Auffinger, Antonio; Chen, Wei-Kuo, The {L}egendre structure of the {P}arisi formula, Comm. Math. Phys.. Communications in Mathematical Physics, 348, 751-770 (2016) · Zbl 1362.82029 · doi:10.1007/s00220-016-2673-0
[4] Achlioptas, D.; Chtcherba, A.; Istrate, G.; Moore, C., The phase transition in 1-in-\(k\)-{SAT} and {NAE}-3-{SAT}. Proc. 12th SODA, ACM-SIAM, 721-722 (2001) · Zbl 0991.68032 · doi:10.1109/FOCS.2008.11
[5] Auffinger, Antonio; Chen, Wei-Kuo; Zeng, Qiang, The {SK} model is infinite step replica symmetry breaking at zero temperature, Comm. Pure Appl. Math.. Communications on Pure and Applied Mathematics, 73, 921-943 (2020) · Zbl 1453.82088 · doi:10.1002/cpa.21886
[6] Aldous, David; Lyons, Russell, Processes on unimodular random networks, Electron. J. Probab.. Electronic Journal of Probability, 12, 1454-1508 (2007) · Zbl 1131.60003 · doi:10.1214/EJP.v12-463
[7] Achlioptas, D.; Moore, C., The asymptotic order of the random \(k\)-{SAT} threshold. Proc. 43rd FOCS, 779-788 (2002) · doi:10.1109/SFCS.2002.1182003
[8] Achlioptas, Dimitris; Peres, Yuval, The threshold for random {\(k\)}-{SAT} is {\(2^k(\ln 2-O(k))\)}. Proceedings of the {T}hirty-{F}ifth {A}nnual {ACM} {S}ymposium on {T}heory of {C}omputing, 223-231 (2003) · Zbl 1192.68333 · doi:10.1145/780542.780577
[9] Bollob\'{a}s, B\'{e}la; Borgs, Christian; Chayes, Jennifer T.; Kim, Jeong Han; Wilson, David B., The scaling window of the 2-{SAT} transition, Random Structures Algorithms. Random Structures & Algorithms, 18, 201-256 (2001) · Zbl 0979.68053 · doi:10.1002/rsa.1006
[10] Bordenave, Charles; Caputo, Pietro, Large deviations of empirical neighborhood distribution in sparse random graphs, Probab. Theory Related Fields. Probability Theory and Related Fields, 163, 149-222 (2015) · Zbl 1327.60067 · doi:10.1007/s00440-014-0590-8
[11] Bapst, Victor; Coja-Oghlan, Amin; Hetterich, Samuel; Ra{\ss}mann, Felicia; Vilenchik, Dan, The condensation phase transition in random graph coloring. Approximation, Randomization, and Combinatorial Optimization, LIPIcs. Leibniz Int. Proc. Inform., 28, 449-464 (2014) · Zbl 1398.68213 · doi:10.4230/LIPIcs.APPROX-RANDOM.2016.22
[12] Bapst, Victor; Coja-Oghlan, Amin, The condensation phase transition in the regular {\(k\)}-{SAT} model. Approximation, Randomization, and Combinatorial Optimization. {A}lgorithms and Techniques, LIPIcs. Leibniz Int. Proc. Inform., 60, 22-18 (2016) · Zbl 1398.68213
[13] Braunstein, A.; M\'{e}zard, M.; Zecchina, R., Survey propagation: an algorithm for satisfiability, Random Structures Algorithms. Random Structures & Algorithms, 27, 201-226 (2005) · Zbl 1087.68126 · doi:10.1002/rsa.20057
[14] Bollob\'{a}s, B\'{e}la, A probabilistic proof of an asymptotic formula for the number of labelled regular graphs, European J. Combin.. European Journal of Combinatorics, 1, 311-316 (1980) · Zbl 0457.05038 · doi:10.1016/S0195-6698(80)80030-8
[15] Benjamini, Itai; Schramm, Oded, Recurrence of distributional limits of finite planar graphs, Electron. J. Probab.. Electronic Journal of Probability, 6, 13 pp. pp. (2001) · Zbl 1010.82021 · doi:10.1214/EJP.v6-96
[16] Cheeseman, P.; Kanefsky, B.; Taylor, W., Where the Really Hard Problems Are, Proc. 12th IJCAI, 331-337 (1991) · Zbl 0747.68064
[17] Coja-Oghlan, Amin, A better algorithm for random {\(k\)}-{SAT}. Automata, Languages and Programming. {P}art {I}, Lecture Notes in Comput. Sci., 5555, 292-303 (2009) · Zbl 1248.68452 · doi:10.1007/978-3-642-02927-1_25
[18] Coja-Oghlan, Amin; Panagiotou, Konstantinos, Catching the {\(k\)}-{NAESAT} threshold [extended abstract]. S{TOC}’12—{P}roceedings of the 2012 {ACM} {S}ymposium on {T}heory of {C}omputing, 899-907 (2012) · Zbl 1286.68185 · doi:10.1145/2213977.2214058
[19] Coja-Oghlan, Amin; Panagiotou, Konstantinos, Going after the {\(k\)}-{SAT} threshold (extended abstract). S{TOC}’13—{P}roceedings of the 2013 {ACM} {S}ymposium on {T}heory of {C}omputing, 705-714 (2013) · Zbl 1293.68164 · doi:10.1145/2488608.2488698
[20] Coja-Oghlan, Amin; Panagiotou, Konstantinos, The asymptotic {\(k\)}-{SAT} threshold, Adv. Math.. Advances in Mathematics, 288, 985-1068 (2016) · Zbl 1394.60007 · doi:10.1016/j.aim.2015.11.007
[21] Chen, Wei-Kuo; Panchenko, Dmitry; Subag, Eliran, The generalized {TAP} free energy {II}, Comm. Math. Phys.. Communications in Mathematical Physics, 381, 257-291 (2021) · Zbl 1456.82762 · doi:10.1007/s00220-020-03887-x
[22] Chv{\'a}tal, V.; Reed, B., Mick gets some (the odds are on his side) (satisfiability). Proc. 33rd Annual Symposium on Foundations of Computer Science, IEEE, 620-627 (1992) · Zbl 0977.68538 · doi:10.1109/SFCS.1992.267789
[23] Ding, Jian; Sly, Allan; Sun, Nike, Satisfiability threshold for random regular {NAE-SAT}. Proc. 46th ACM Symposium on Theory of Computing, STOC ’14, ACM, 814-822 (2013) · Zbl 1315.68148 · doi:10.1145/2591796.2591862
[24] Ding, Jian; Sly, Allan; Sun, Nike, Maximum independent sets on random regular graphs, Acta Math.. Acta Mathematica, 217, 263-340 (2016) · Zbl 1371.05261 · doi:10.1007/s11511-017-0145-9
[25] Ding, Jian; Sly, Allan; Sun, Nike, Satisfiability threshold for random regular {NAE}-{SAT}, Comm. Math. Phys.. Communications in Mathematical Physics, 341, 435-489 (2016) · Zbl 1335.68243 · doi:10.1007/s00220-015-2492-8
[26] Franz, Silvio; Leone, Michele, Replica bounds for optimization problems and diluted spin systems, J. Statist. Phys.. Journal of Statistical Physics, 111, 535-564 (2003) · Zbl 1049.82070 · doi:10.1023/A:1022885828956
[27] Franco, John; Paull, Marvin, Probabilistic analysis of the {D}avis-{P}utnam procedure for solving the satisfiability problem, Discrete Appl. Math.. Discrete Applied Mathematics. The Journal of Combinatorial Algorithms, Informatics and Computational Sciences, 5, 77-87 (1983) · Zbl 0497.68021 · doi:10.1016/0166-218X(83)90017-3
[28] Friedgut, Ehud, Sharp thresholds of graph properties, and the {\(k\)}-sat problem, J. Amer. Math. Soc.. Journal of the American Mathematical Society, 12, 1017-1054 (1999) · Zbl 0932.05084 · doi:10.1090/S0894-0347-99-00305-7
[29] Goerdt, Andreas, A threshold for unsatisfiability. Mathematical foundations of computer science 1992 ({P}rague, 1992), Lecture Notes in Comput. Sci., 629, 264-274 (1992) · Zbl 1494.68095 · doi:10.1007/3-540-55808-X_25
[30] Gamarnik, David; Sudan, Madhu, Limits of local algorithms over sparse random graphs [extended abstract]. I{TCS}’14—{P}roceedings of the 2014 {C}onference on {I}nnovations in {T}heoretical {C}omputer {S}cience, 369-375 (2014) · Zbl 1365.05277 · doi:10.1145/2554797.2554831
[31] Guerra, Francesco; Toninelli, Fabio Lucio, The thermodynamic limit in mean field spin glass models, Comm. Math. Phys.. Communications in Mathematical Physics, 230, 71-79 (2002) · Zbl 1004.82004 · doi:10.1007/s00220-002-0699-y
[32] Guerra, Francesco, Broken replica symmetry bounds in the mean field spin glass model, Comm. Math. Phys.. Communications in Mathematical Physics, 233, 1-12 (2003) · Zbl 1013.82023 · doi:10.1007/s00220-002-0773-5
[33] Jagannath, Aukosh; Tobasco, Ian, A dynamic programming approach to the {P}arisi functional, Proc. Amer. Math. Soc.. Proceedings of the American Mathematical Society, 144, 3135-3150 (2016) · Zbl 1376.60081 · doi:10.1090/proc/12968
[34] Karp, Richard M., Reducibility among combinatorial problems. Complexity of Computer Computations, 85-103 (1972) · Zbl 1467.68065 · doi:10.1007/978-1-4684-2001-2_9
[35] Kirousis, Lefteris M.; Kranakis, Evangelos; Krizanc, Danny; Stamatiou, Yannis C., Approximating the unsatisfiability threshold of random formulas, Random Structures Algorithms. Random Structures & Algorithms, 12, 253-269 (1998) · Zbl 0936.68038 · doi:url = {https://doi.org/ckgwrv
[36] Krz{\c{a}}ka{\l{a}}, Florent; Montanari, Andrea; Ricci-Tersenghi, Federico; Semerjian, Guilhem; Zdeborov\'{a}, Lenka, Gibbs states and the set of solutions of random constraint satisfaction problems, Proc. Natl. Acad. Sci. USA. Proceedings of the National Academy of Sciences of the United States of America, 104, 10318-10323 (2007) · Zbl 1190.68031 · doi:10.1073/pnas.0703685104
[37] Levin, Leonid A., Average case complete problems, SIAM J. Comput.. SIAM Journal on Computing, 15, 285-286 (1986) · Zbl 0589.68032 · doi:10.1137/0215020
[38] Lyons, Russell; Pemantle, Robin; Peres, Yuval, Ergodic theory on {G}alton-{W}atson trees: speed of random walk and dimension of harmonic measure, Ergodic Theory Dynam. Systems. Ergodic Theory and Dynamical Systems, 15, 593-619 (1995) · Zbl 0819.60077 · doi:10.1017/S0143385700008543
[39] M\'{e}zard, Marc; Montanari, Andrea, Information, Physics, and Computation, Oxford Grad. Texts, xiv+569 pp. (2009) · Zbl 1163.94001 · doi:10.1093/acprof:oso/9780198570837.001.0001
[40] Maneva, Elitza; Mossel, Elchanan; Wainwright, Martin J., A new look at survey propagation and its generalizations, J. ACM. Journal of the ACM, 54, 17-41 (2007) · Zbl 1312.68175 · doi:10.1145/1255443.1255445
[41] Mertens, Stephan; M\'{e}zard, Marc; Zecchina, Riccardo, Threshold values of random {\(K\)}-{SAT} from the cavity method, Random Structures Algorithms. Random Structures & Algorithms, 28, 340-373 (2006) · Zbl 1094.68035 · doi:10.1002/rsa.20090
[42] Montanari, Andrea, Optimization of the {S}herrington-{K}irkpatrick {H}amiltonian. 2019 {IEEE} 60th {A}nnual {S}ymposium on {F}oundations of {C}omputer {S}cience, 1417-1433 (2019) · doi:10.1109/FOCS.2019.00087
[43] M\'{e}zard, Marc; Parisi, Giorgio, Replicas and optimization, J. Phys. Lett., 46, 771-778 (1985) · doi:10.1051/jphyslet:019850046017077100
[44] M\'{e}zard, Marc; Parisi, Giorgio; Virasoro, Miguel Angel, Spin Glass Theory and Beyond: An Introduction to the Replica Method and its Applications, World Sci. Lect. Notes Phys., 9, xiv+461 pp. (1987) · Zbl 0992.82500 · doi:10.1142/0271
[45] M\'{e}zard, Marc; Parisi, Giorgio; Zecchina, R., Analytic and algorithmic solution of random satisfiability problems, Science, 297, 812-815 (2002) · doi:10.1126/science.1073287
[46] Montanari, A.; Ricci-Tersenghi, F.; Semerjian, G., Clusters of solutions and replica symmetry breaking in random \(k\)-satisfiability, J. Stat. Mech. Theory E.. Journal of Statistical Mechanics: Theory and Experiment, 2008, 44 pp. pp. (2008) · doi:10.1088/1742-5468/2008/04/p04004
[47] M\'{e}zard, M.; Ricci-Tersenghi, F.; Zecchina, R., Two solutions to diluted {\(p\)}-spin models and {XORSAT} problems, J. Statist. Phys.. Journal of Statistical Physics, 111, 505-533 (2003) · Zbl 1049.82073 · doi:10.1023/A:1022886412117
[48] Mitchell, D.; Selman, B.; Levesque, H., Hard and easy distributions of {SAT} problems, Proc. 10th AAAI, 92, 459-465 (1992)
[49] Panchenko, Dmitry, The {P}arisi ultrametricity conjecture, Ann. of Math. (2). Annals of Mathematics. Second Series, 177, 383-393 (2013) · Zbl 1270.60060 · doi:10.4007/annals.2013.177.1.8
[50] Panchenko, Dmitry, The {S}herrington-{K}irkpatrick Model, Springer Monogr. Math., xii+156 pp. (2013) · Zbl 1266.82005 · doi:10.1007/978-1-4614-6289-7
[51] Panchenko, Dmitry, Spin glass models from the point of view of spin distributions, Ann. Probab.. The Annals of Probability, 41, 1315-1361 (2013) · Zbl 1281.60081 · doi:10.1214/11-AOP696
[52] Panchenko, Dmitry, Structure of 1-{RSB} asymptotic {G}ibbs measures in the diluted {\(p\)}-spin models, J. Stat. Phys.. Journal of Statistical Physics, 155, 1-22 (2014) · Zbl 1291.82058 · doi:10.1007/s10955-014-0955-5
[53] Panchenko, Dmitry, Hierarchical exchangeability of pure states in mean field spin glass models, Probab. Theory Related Fields. Probability Theory and Related Fields, 161, 619-650 (2015) · Zbl 1320.60159 · doi:10.1007/s00440-014-0555-y
[54] Parisi, Giorgio, Infinite number of order parameters for spin-glasses, Phys. Rev. Lett.. Physical Review Letters, 43, 1754 pp. (1979) · doi:10.1103/PhysRevLett.43.1754
[55] Parisi, Giorgio, The order parameter for spin glasses: A function on the interval 0-1, J. Phys. A, 13, 1101-1112 (1980) · doi:10.1088/0305-4470/13/3/042
[56] Parisi, Giorgio, A sequence of approximated solutions to the {SK} model for spin glasses, J. Phys. A, 13, L115-L121 (1980) · doi:10.1088/0305-4470/13/4/009
[57] Parisi, Giorgio, Order parameter for spin-glasses, Phys. Rev. Lett.. Physical Review Letters, 50, 1946-1948 (1983) · doi:10.1103/PhysRevLett.50.1946
[58] Parisi, Giorgio, On local equilibrium equations for clustering states (2005)
[59] Pittel, Boris; Sorkin, Gregory B., The satisfiability threshold for {\(k\)}-{XORSAT}, Combin. Probab. Comput.. Combinatorics, Probability and Computing, 25, 236-268 (2016) · Zbl 1372.68193 · doi:10.1017/S0963548315000097
[60] Panchenko, Dmitry; Talagrand, Michel, Bounds for diluted mean-fields spin glass models, Probab. Theory Related Fields. Probability Theory and Related Fields, 130, 319-336 (2004) · Zbl 1101.82041 · doi:10.1007/s00440-004-0342-2
[61] Rockafellar, R. Tyrrell, Convex Analysis, Princeton Math. Series, Princeton Landmarks in Math., xviii+451 pp. (1997) · Zbl 0932.90001
[62] Sherrington, D.; Kirkpatrick, S., Solvable model of a spin-glass, Phys. Rev. Lett., 35, 1792-1796 (1975) · doi:10.1103/PhysRevLett.35.1792
[63] Sly, Allan; Sun, Nike; Zhang, Yumeng, The number of solutions for random regular {NAE}-{SAT}. 57th {A}nnual {IEEE} {S}ymposium on {F}oundations of {C}omputer {S}cience—{FOCS} 2016, 724-731 (2016) · doi:10.1109/FOCS.2016.82
[64] Subag, Eliran, Following the ground states of full-{RSB} spherical spin glasses, Comm. Pure Appl. Math.. Communications on Pure and Applied Mathematics, 74, 1021-1044 (2021) · Zbl 1467.82097 · doi:10.1002/cpa.21922
[65] Talagrand, Michel, The {P}arisi formula, Ann. of Math. (2). Annals of Mathematics. Second Series, 163, 221-263 (2006) · Zbl 1137.82010 · doi:10.4007/annals.2006.163.221
[66] Talagrand, Michel, Mean field models for spin glasses. Basic Examples. {V}olume {I}, Ergeb. Math. Grenzgeb., 54, xviii+485 pp. (2011) · Zbl 1214.82002 · doi:10.1007/978-3-642-15202-3
[67] Wormald, N. C., Models of random regular graphs. Surveys in Combinatorics, 1999, London Math. Soc. Lecture Note Ser., 267, 239-298 (1999) · Zbl 0935.05080 · doi:10.1017/CBO9780511721335.010
[68] Yedidia, Jonathan S.; Freeman, William T.; Weiss, Yair, Constructing free-energy approximations and generalized belief propagation algorithms, IEEE Trans. Inform. Theory. Institute of Electrical and Electronics Engineers. Transactions on Information Theory, 51, 2282-2312 (2005) · Zbl 1283.94023 · doi:10.1109/TIT.2005.850085
[69] Zdeborov\'{a}, Lenka; Krz\c{a}ka\l{a}, Florent, Phase transitions in the coloring of random graphs, Phys. Rev. E). Physical Review E. Statistical, Nonlinear, and Soft Matter Physics, 76, 031131-1 (2007) · doi:10.1103/PhysRevE.76.031131
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.