Random Constraint Satisfaction Problems

Amin Coja-Oghlan

Random instances of constraint satisfaction problems such as k-SAT provide challenging benchmarks. If there are m constraints over n variables there is typically a large range of densities r=m/n where solutions are known to exist with probability close to one due to non-constructive arguments. However, no algorithms are known to find solutions efficiently with a non-vanishing probability at even much lower densities. This fact appears to be related to a phase transition in the set of all solutions. The goal of this extended abstract is to provide a perspective on this phenomenon, and on the computational challenge that it poses.

In S. Barry Cooper and Vincent Danos: Proceedings Fifth Workshop on Developments in Computational Models — Computational Models From Nature (DCM 2009), Rhodes, Greece, 11th July 2009, Electronic Proceedings in Theoretical Computer Science 9, pp. 32–37.
Published: 15th November 2009.

ArXived at: http://dx.doi.org/10.4204/EPTCS.9.4 bibtex PDF

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org