Silvio Franz, Giorgio Parisi, Maksim Sevelev, Pierfrancesco Urbani, Francesco Zamponi
SciPost Phys. 2, 019 (2017) ·
published 2 June 2017
|
· pdf
Random constraint satisfaction problems (CSP) have been studied extensively
using statistical physics techniques. They provide a benchmark to study average
case scenarios instead of the worst case one. The interplay between statistical
physics of disordered systems and computer science has brought new light into
the realm of computational complexity theory, by introducing the notion of
clustering of solutions, related to replica symmetry breaking. However, the
class of problems in which clustering has been studied often involve discrete
degrees of freedom: standard random CSPs are random K-SAT (aka disordered Ising
models) or random coloring problems (aka disordered Potts models). In this work
we consider instead problems that involve continuous degrees of freedom. The
simplest prototype of these problems is the perceptron. Here we discuss in
detail the full phase diagram of the model. In the regions of parameter space
where the problem is non-convex, leading to multiple disconnected clusters of
solutions, the solution is critical at the SAT/UNSAT threshold and lies in the
same universality class of the jamming transition of soft spheres. We show how
the critical behavior at the satisfiability threshold emerges, and we compute
the critical exponents associated to the approach to the transition from both
the SAT and UNSAT phase. We conjecture that there is a large universality class
of non-convex continuous CSPs whose SAT-UNSAT threshold is described by the
same scaling solution.
