Approximating satisfiability transition by suppressing fluctuations

2004/03/17 by S. Knysh, Sergey Knysh, V.N. Smelyanskiy +6 · 1 citation
Computer Science · Physics and Astronomy · #Advanced Graph Theory Research #Computability, Logic, AI Algorithms #Constraint Satisfaction and Optimization #cond-mat.dis-nn #cond-mat.stat-mech

paper · pdf · doi:10.48550/arxiv.cond-mat/0403416

31 pages, 6 figures

arxiv created 2004/03/17 · arxiv updated 2009/12/01

Abstract

Using methods and ideas from statistical mechanics, we propose a simple method for obtaining rigorous upper bounds for satisfiability transition in random boolean expressions composed of N variables and M clauses with K variables per clause. Determining the location of satisfiability threshold α_c=M/N for a number of difficult combinatorial problems is a major open problem in the theory of random graphs. The method is based on identification of the core -- a subexpression (subgraph) that has the same satisfiability properties as the original expression. We formulate self-consistency equations that determine macroscopic parameters of the core and compute an improved annealing bound. We illustrate the method for three sample problems: K-XOR-SAT, K-SAT and positive 1-in-K-SAT.

Cited by

• Typical case behaviour of spin systems in random graph and composite ensembles

Related

• Proof of the satisfiability conjecture for large k
• Satisfiability threshold for random regular NAE-SAT
• Generalised and Quotient Models for Random And/Or Trees and Application to Satisfiability
• The Satisfiability Threshold of Random 3-SAT Is at Least 3.52
• Some Results on Random Mixed SAT Problems