Using a Parisi ansatz in the unsatisfiable phase of constraint satisfaction problems.

Abstract

Constraint satisfaction problems are ubiquitous in fields ranging from the physics of solids to artificial intelligence. In many cases, such systems undergo a transition when the ratio of constraints to variables reaches some value α_{crit}. Above this critical value, it is exponentially unlikely that all constraints can be mutually satisfied. We calculate the probability that constraints can all be satisfied, P(SAT), for the spherical perceptron. Traditional replica methods, such as the Parisi ansatz, fall short. We find a new ansatz, the jammed Parisi ansatz, that correctly describes the behavior of the system in this regime. With the jammed Parisi ansatz, we calculate P(SAT) for the first time and match previous computations of thresholds. We anticipate that the techniques developed here will be applicable to general constraint satisfaction problems and the identification of hidden structures in datasets.