On the K‐sat model with large number of clauses. Issue 3 (26th November 2017)

• Record Type: Journal Article
• Authors: Panchenko, Dmitry
• Is Part Of: Random structures & algorithms. Volume 52:Issue 3(2018)
• Page Start: 536
• Page End: 542
• Publication Date: 2017-11-26
• Subjects: K‐sat model -- p‐spin models -- spin glasses; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20748
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: We show that in the K ‐sat model with N variables and αN clauses, the expected ratio of the smallest number of unsatisfied clauses to the number of variables is α / 2 K − α c ∗ ( N ) / 2 K up to smaller order terms o ( α ) as α → ∞ uniformly in N, where c ∗ ( N ) is the expected normalized maximum energy of some specific mixed p ‐spin spin glass model. The formula for the limit of c ∗ ( N ) is well known in the theory of spin glasses.