Some remarks on the survey decimation algorithm for K-satisfiability
Parisi, Giorgio
Computational Complexity
Disordered Systems and Neural Networks
Data Structures and Algorithms
G.3, G.2.1
Original · EN
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.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.