skip to main content
10.1145/2591796.2591862acmconferencesArticle/Chapter ViewAbstractPublication PagesstocConference Proceedingsconference-collections
research-article

Satisfiability threshold for random regular NAE-SAT

Published: 31 May 2014 Publication History

Abstract

We consider the random regular k-nae-sat problem with n variables each appearing in exactly d clauses. For all k exceeding an absolute constant k0, we establish explicitly the satisfiability threshold d*d*(k). We prove that for d < d* the problem is satisfiable with high probability while for d > d* the problem is unsatisfiable with high probability. If the threshold d* lands exactly on an integer, we show that the problem is satisfiable with probability bounded away from both zero and one. This is the first result to locate the exact satisfiability threshold in a random constraint satisfaction problem exhibiting the condensation phenomenon identified by Krzakał a et al. (2007). Our proof verifies the onestep replica symmetry breaking formalism for this model. We expect our methods to be applicable to a broad range of random constraint satisfaction problems and combinatorial problems on random graphs.

Supplementary Material

MP4 File (p814-sidebyside.mp4)

References

[1]
D. Achlioptas and C. Moore. Random k-sat: two moments suffice to cross a sharp threshold. SIAM J. Comput., 36(3):740--762 (electronic), 2006.
[2]
D. Achlioptas, A. Naor, and Y. Peres. Rigorous location of phase transitions in hard optimization problems. Nature, 435(7043):759--764, 2005.
[3]
D. Achlioptas and Y. Peres. The threshold for random k-sat is 2k log 2 --- O(k). J. Amer. Math. Soc., 17(4):947--973 (electronic), 2004.
[4]
D. Achlioptas and F. Ricci-Tersenghi. Random formulas have frozen variables. SIAM J. Comput., 39(1):260--280, 2009.
[5]
E. Aurell, U. Gordon, and S. Kirkpatrick. Comparing beliefs, surveys, and random walks. In NIPS, 2004.
[6]
A. Braunstein, M. Mézard, and R. Zecchina. Survey propagation: an algorithm for satisfiability. Random Struct. Algor., 27(2):201--226, 2005.
[7]
A. Braunstein and R. Zecchina. Survey propagation as local equilibrium equations. J. Stat. Mech. Theory E., 2004(06):P06007, 2004.
[8]
T. Castellani, V. Napolano, F. Ricci-Tersenghi, and R. Zecchina. Bicolouring random hypergraphs. J. Phys. A, 36(43):11037--11053, 2003.
[9]
V. Chvátal and B. Reed. Mick gets some (the odds are on his side). In Proc. IEEE Symp. (FOCS), pages 620--627, 1992.
[10]
A. Coja-Oghlan. Random regular k-sat. Preprint at http://arxiv.org/abs/1310.2728v1, 2013.
[11]
A. Coja-Oghlan. The asymptotic k-sat threshold. In Proc. ACM Symp. (STOC), 2014.
[12]
A. Coja-Oghlan and K. Panagiotou. Catching the k-naesat threshold. In Proc. ACM Symp. (STOC), pages 899--907. ACM, New York, 2012.
[13]
A. Coja-Oghlan and K. Panagiotou. Going after the k-sat threshold. In Proc. ACM Symp. (STOC), pages 705--714, New York, NY, USA, 2013. ACM.
[14]
A. Coja-Oghlan and D. Vilenchik. Chasing the k-colorability threshold. In Proc. IEEE Symp. (FOCS), pages 380--389, Oct 2013.
[15]
A. Coja-Oghlan and L. Zdeborová. The condensation transition in random hypergraph 2-coloring. In Proc. ACM-SIAM Symp. (SODA), pages 241--250. SIAM, 2012.
[16]
L. Dall'Asta, A. Ramezanpour, and R. Zecchina. Entropy landscape and non-Gibbs solutions in constraint satisfaction problems. Phys. Rev. E (3), 77(3):031118, 16, 2008.
[17]
A. Dembo, A. Montanari, A. Sly, and N. Sun. The replica symmetric solution for Potts models on d-regular graphs. Comm. Math. Phys., 2014.
[18]
A. Dembo, A. Montanari, and N. Sun. Factor models on locally tree-like graphs. Ann. Probab., 41(6):4162--4213, 2013.
[19]
J. Ding, A. Sly, and N. Sun. Maximum independent sets on random regular graphs. Preprint at http://arxiv.org/abs/1310.4787, 2013.
[20]
W. Fernandez de la Vega. Random 2-sat: results and problems. Theoretical Computer Science, 265(1):131--146, 2001.
[21]
E. Friedgut. Sharp thresholds of graph properties, and the k-sat problem. J. Amer. Math. Soc., 12(4):1017--1054, 1999. With an appendix by Jean Bourgain.
[22]
A. Galanis, D. Štefankovič, and E. Vigoda. Inapproximability for antiferromagnetic spin systems in the tree non-uniqueness region. In Proc. ACM Symp. (STOC), 2014.
[23]
A. Goerdt. A threshold for unsatisfiability. J. Comput. System Sci., 53(3):469--486, 1996.
[24]
S. Janson, T. Łuczak, and A. Rucinski. Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000.
[25]
F. Krzakała, A. Montanari, F. Ricci-Tersenghi, G. Semerjian, and L. Zdeborová. Gibbs states and the set of solutions of random constraint satisfaction problems. P. Natl. Acad. Sci., 104(25):10318--10323, 2007.
[26]
E. Maneva, E. Mossel, and M. J. Wainwright. A new look at survey propagation and its generalizations. J. ACM, 54(4):Art. 17, 41, 2007.
[27]
E. Maneva and A. Sinclair. On the satisfiability threshold and clustering of solutions of random 3-sat formulas. Theoret. Comput. Sci., 407(1-3):359--369, 2008.
[28]
M. Mézard and A. Montanari. Information, physics, and computation. Oxford Graduate Texts. Oxford University Press, Oxford, 2009.
[29]
M. Mézard, T. Mora, and R. Zecchina. Clustering of solutions in the random satisfiability problem. Phys. Rev. Lett., 94(19):197205, 2005.
[30]
M. Mézard and G. Parisi. Replicas and optimization. Journal de Physique Lettres, 46(17):771--778, 1985.
[31]
M. Mézard and G. Parisi. The Bethe lattice spin glass revisited. Eur. Phys. J. B, 20(2):217--233, 2001.
[32]
M. Mézard and G. Parisi. The cavity method at zero temperature. J. Stat. Phys., 111(1-2):1--34, 2003.
[33]
M. Mézard, G. Parisi, and R. Zecchina. Analytic and algorithmic solution of random satisfiability problems. Science, 297(5582):812--815, 2002.
[34]
M. Mézard, F. Ricci-Tersenghi, and R. Zecchina. Two solutions to diluted p-spin models and xorsat problems. J. Stat. Phys., 111(3-4):505--533, 2003.
[35]
M. Molloy and R. Restrepo. Frozen variables in random boolean constraint satisfaction problems. In Proc. ACM Symp. (SODA), pages 1306--1318. SIAM, 2013.
[36]
R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman, and L. Troyansky. Determining computational complexity from characteristic "phase transitions". Nature, 400(6740):133--137, 1999.
[37]
A. Montanari, F. Ricci-Tersenghi, and G. Semerjian. Clusters of solutions and replica symmetry breaking in random k-satisfiability. J. Stat. Mech. Theory E., 2008(04):P04004, 2008.
[38]
B. Pittel and G. B. Sorkin. The satisfiability threshold for k-xorsat. Preprint at http://arxiv.org/abs/1212.1905, 2012.
[39]
R. W. Robinson and N. C. Wormald. Almost all cubic graphs are Hamiltonian. Random Struct. Algor., 3(2):117--125, 1992.
[40]
R. W. Robinson and N. C. Wormald. Almost all regular graphs are Hamiltonian. Random Struct. Algor., 5(2):363--374, 1994.
[41]
N. C. Wormald. Models of random regular graphs. In Surveys in combinatorics, 1999 (Canterbury), volume 267 of London Math. Soc. Lecture Note Ser., pages 239--298. Cambridge Univ. Press, Cambridge, 1999.

Cited By

View all
  • (2023)Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00026(307-327)Online publication date: 6-Nov-2023
  • (2023)Designing Ising machines with higher order spin interactions and their application in solving combinatorial optimizationScientific Reports10.1038/s41598-023-36531-413:1Online publication date: 12-Jun-2023
  • (2021)The Phase Transition Analysis for the Random Regular Exact 2-(d, k)-SAT ProblemSymmetry10.3390/sym1307123113:7(1231)Online publication date: 8-Jul-2021
  • Show More Cited By

Index Terms

  1. Satisfiability threshold for random regular NAE-SAT

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    STOC '14: Proceedings of the forty-sixth annual ACM symposium on Theory of computing
    May 2014
    984 pages
    ISBN:9781450327107
    DOI:10.1145/2591796
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 31 May 2014

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. condensation
    2. constraint satisfaction problem
    3. replica symmetry breaking
    4. satisfiability threshold
    5. survey propagation

    Qualifiers

    • Research-article

    Funding Sources

    Conference

    STOC '14
    Sponsor:
    STOC '14: Symposium on Theory of Computing
    May 31 - June 3, 2014
    New York, New York

    Acceptance Rates

    STOC '14 Paper Acceptance Rate 91 of 319 submissions, 29%;
    Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

    Upcoming Conference

    STOC '25
    57th Annual ACM Symposium on Theory of Computing (STOC 2025)
    June 23 - 27, 2025
    Prague , Czech Republic

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)22
    • Downloads (Last 6 weeks)1
    Reflects downloads up to 13 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2023)Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00026(307-327)Online publication date: 6-Nov-2023
    • (2023)Designing Ising machines with higher order spin interactions and their application in solving combinatorial optimizationScientific Reports10.1038/s41598-023-36531-413:1Online publication date: 12-Jun-2023
    • (2021)The Phase Transition Analysis for the Random Regular Exact 2-(d, k)-SAT ProblemSymmetry10.3390/sym1307123113:7(1231)Online publication date: 8-Jul-2021
    • (2021)Frozen 1-RSB structure of the symmetric Ising perceptronProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451119(1579-1588)Online publication date: 15-Jun-2021
    • (2021)The number of solutions for random regular NAE-SATProbability Theory and Related Fields10.1007/s00440-021-01029-5Online publication date: 20-Nov-2021
    • (2018) The Number of Satisfying Assignments of Random Regular k -SAT Formulas Combinatorics, Probability and Computing10.1017/S096354831800026327:4(496-530)Online publication date: 20-Jun-2018
    • (2017)Phase Transition for Maximum Not-All-Equal SatisfiabilityFrontiers in Algorithmics10.1007/978-3-319-59605-1_24(267-279)Online publication date: 23-May-2017
    • (2016)The Number of Solutions for Random Regular NAE-SAT2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2016.82(724-731)Online publication date: Oct-2016
    • (2016)Harnessing the Bethe free energyRandom Structures & Algorithms10.1002/rsa.2069249:4(694-741)Online publication date: 21-Oct-2016
    • (2015)Proof of the Satisfiability Conjecture for Large kProceedings of the forty-seventh annual ACM symposium on Theory of Computing10.1145/2746539.2746619(59-68)Online publication date: 14-Jun-2015
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media