This chapter studies an ensemble of random satisfiability problems, ‘random K-satisfiability’ (K-SAT). Applying the 1RSB cavity method, it first derives the phase diagram in the limit of large N, in particular the location of the SAT-UNSAT threshold. Within the SAT phase, the chapter focuses on the intermediate clustered phase close, and computes the number of clusters to leading exponential order in N. The application of survey propagation to this problem is then described. Combined with a simple decimation procedure, the chapter provides an efficient method for finding satisfiable assignments in the clustered phase. The whole chapter is based on heuristic arguments. There is not yet any rigorous proof of the results presented, neither concerning the phase diagram, nor the convergence properties of message passing algorithms and their use in decimation procedures.
Oxford Scholarship Online requires a subscription or purchase to access the full text of books within the service. Public users can however freely search the site and view the abstracts and keywords for each book and chapter.
If you think you should have access to this title, please contact your librarian.