  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.
