Some remarks on the survey decimation algorithm for K-satisfiability

Abstract

In this note we study the convergence of the survey decimation algorithm. An analytic formula for the reduction of the complexity during the decimation is derived. The limit of the converge of the algorithm are estimated in the random case: interesting phenomena appear near the boundary of convergence.

References in corpus (2)

• The Entropy of the K-Satisfiability Problem
• A variational description of the ground state structure in random satisfiability problems

Cited by in corpus (7)

• Optimization hardness as transient chaos in an analog approach to constraint satisfaction
• The backtracking survey propagation algorithm for solving random K-SAT problems
• Efficient Solution of Boolean Satisfiability Problems with Digital MemComputing
• Minimizing energy below the glass thresholds
• Approximate analysis of search algorithms with "physical" methods
• Constraint Optimization and Statistical Mechanics
• Statistical mechanics of optimization problems