On Generalized Survey Propagation: Normal Realization and Sum-Product Interpretation

A celebrated algorithmic discovery in solving constraint satisfaction problems, survey propagation (SP) and its generalization have recently demonstrated their power in areas of communications and data compression. It is known that under certain Markov random field (MRF) formalism of k-SAT problems, SP may be interpreted as an instance of belief propagation (BP). In this paper, we borrow the notion of generalized states from system theory and coding theory, and introduce a new MRF formalism - normal realization - for k-SAT problems. We show that when BP applies to this MRF, generalized SP is resulted. This new MRF formalism appears to be simpler than the existing one and the interpretation of SP as BP in this framework also appears more transparent

I. Introduction

At the heart of the theory of computation, -SAT problems are classical NP-complete problems [1]. Extensive study has been carried out in order to understand the hardness of these problems and to develop efficient solvers. A recent celebrated result in -SAT problems is the work of Mézard Parisi and Zecchina [2], published in Science, where a highly efficient algorithm — derived from techniques in statistical physics — was introduced. As shown in [2] and various follow-up developments (see, e.g., [3]), this algorithm remains effective even for very large and difficult instances of random -SAT problems. The central part of this algorithm is an iterative message-passing procedure — known as survey propagation — that operates on the Jactor-graph representation [4] of the problem instance.