On the K‐sat model with large number of clauses

DOI10.1002/RSA.20748MaRDI QIDQ4642745zbMATH OpenOpenAlexFDO

Authors D. Panchenko

Publication date 25 May 2018

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.06256

zbMATH Keywords

\(K\)-sat model\(p\)-spin modelsspin glasses

Mathematics Subject Classification ID

Combinatorial probability (60C05)

Abstract: We show that in the $K$-sat model with $N$ variables and $alphaN$ clauses, the expected ratio of the smallest number of unsatisfied clauses to the number of variables is $alpha/2^K-sqrtalpha{c}_{\ast }(N)/2^K$ up to smaller order terms $o(sqrtalpha)$ as $alphaoinfty$ uniformly in $N$, where $c_{\ast }(N)$ is the expected normalized maximum energy of some specific mixed $p$-spin spin glass model. The formula for the limit of $c_{\ast }(N)$ is well known in the theory of spin glasses.

Recommendations

• On the complexity of k-SAT
• On k-positive satisfiability problem
• Complexity and Algorithms for Well-Structured k-SAT Instances
• On the parameterized complexity of \((k,s)\)-SAT
• Proof of the satisfiability conjecture for large k
• Proof of the satisfiability conjecture for large \(k\)
• The K-SAT problem in a simple limit
• The asymptotic \(k\)-SAT threshold
• The asymptotic k-SAT threshold
• An approximation algorithm for \(\#k\)-SAT

Cited in

(11)

• Disorder chaos in some diluted spin Glass models
• Belief propagation on the random \(k\)-SAT model
• The marginally stable Bethe lattice spin glass revisited
• Suboptimality of local algorithms for a class of max-cut problems
• Can rare SAT formulae be easily recognized? On the efficiency of message-passing algorithms forK-SAT at large clause-to-variable ratios
• Combinatorics. Abstracts from the workshop held January 1--7, 2023
• Optimization algorithms for multi-species spherical spin glasses
• A Friendly Tutorial on Mean-Field Spin Glass Techniques for Non-Physicists
• Tight Lipschitz hardness for optimizing mean field spin glasses
• Bounds on the ground state energy of quantum p-spin Hamiltonians
• On the MCMC performance in Bernoulli group testing and the random max-set cover problem

This page was built for publication: On the K‐sat model with large number of clauses

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4642745)