SciPost logo

SciPost Submission Page

Universality of the SAT-UNSAT (jamming) threshold in non-convex continuous constraint satisfaction problems

by Silvio Franz, Giorgio Parisi, Maksim Sevelev, Pierfrancesco Urbani, Francesco Zamponi

This is not the current version.

Submission summary

As Contributors: Silvio Franz · Maxime Sevelev · Pierfrancesco Urbani
Arxiv Link: https://arxiv.org/abs/1702.06919v1 (pdf)
Date submitted: 2017-02-25 01:00
Submitted by: Urbani, Pierfrancesco
Submitted to: SciPost Physics
Academic field: Physics
Specialties:
  • Computational Complexity
  • Statistical and Soft Matter Physics
Approach: Theoretical

Abstract

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.

Ontology / Topics

See full Ontology or Topics database.

Complexity theory Constraint satisfaction problems (CSP) Disordered systems Ising model Jamming Perceptron Potts model Replica symmetry breaking
Current status:
Has been resubmitted



Reports on this Submission

Anonymous Report 2 on 2017-4-25 (Invited Report)

  • Cite as: Anonymous, Report on arXiv:1702.06919v1, delivered 2017-04-25, doi: 10.21468/SciPost.Report.121

Strengths

It looks like an exemplar piece of theoretical work

Weaknesses

Probably is connected to its strength. It's too technical and hard to follow for somebody without a background in disordered systems.

Report

I must admit that I didn't have the time to properly check all the results presented by the authors, although they look to me reasonable, physically sound and feasible to be reproduced with the technical information provided in the manuscript.

The paper is very well written, the results are original and it probably concludes the analysis of the thermodynamics of the problem already started by the authors and other collaborators in ref's [14], [16]-[19]. Therefore I strongly recommend this work as an important piece in the study of disordered systems with continuous variables.

Requested changes

1-However, I would like to suggest to the authors to make clearer in the conclusions that their statement that the SAT/UNSAT transition is fullRSB, is a statement valid strictly for the model studied in the manuscript and not necessarily valid for other non-convex continuous CSP. At least, in the way that I understood the manuscript. If this is not the case, it is worth to say a few words about why the authors believe this statement is more general than that.

  • validity: top
  • significance: high
  • originality: top
  • clarity: high
  • formatting: perfect
  • grammar: excellent

Author:  Pierfrancesco Urbani  on 2017-04-29  [id 123]

(in reply to Report 2 on 2017-04-25)
Category:
remark

We thank the referee for her/his report. We have followed her/his suggestion and we have added a sentence in the conclusions underlining what she/he was mentioning. We are not able to prove that the non-convex jamming transition is always in a fullRSB phase. Nevertheless there are at least two models where this is the case that are the random perceptron and hard spheres in high dimension. We resubmit an updated version of the paper with very few typos corrected.

Anonymous Report 1 on 2017-4-13 (Contributed Report)

  • Cite as: Anonymous, Report on arXiv:1702.06919v1, delivered 2017-04-13, doi: 10.21468/SciPost.Report.109

Strengths

1- brings together two fields, jamming and constraint satisfaction problems (CSP) with continuous variables

2- paper is complete, detailed and very well written

3- show signatures of universalities in mean field jamming/CSP transitions

4- phase diagram and exponents computed exactly

Weaknesses

1 - The paper is very technical, perhaps a little bit difficult to read by non experts. However all the pointers are given to the readers.

Report

This is an impressive paper which builds a complete and deep connection between jamming transitions and sat/unsat transitions in random constraint satisfaction problems (CSP) with continuous interactions.
The paper is extremely well written. It provides all the physical insights and definitions of the jamming observables which are needed to interpret the full phase diagram of CSP problems in physical terms. The sphere packing problem in high dimension is represented as a perceptron model with appropriate (negative) stability. The corresponding packing problem is highly non convex as in jamming. Quite remarkably the full T=0 phase diagram is derived, including all levels of symmetry breaking.
The analysis is taken to its limits by computing the scaling solution at the SAT phase boundary of the perceptron. The scaling relations between critical exponents is interpreted in terms of gaps and force distribution at the jamming point.

In my opinion, this paper deserves publication in its present form. There is no doubt that it provides an important unifying perspective on jamming transitions at mean-field level. Moreover is also provides new insight for random CSPs with continuous variables.

The fact that the perceptron model and hard spheres have the same mean field exponents (in infinite dimension) is important. The authors outline some interesting perspectives for future studies aimed at establishing the degree of universality of these results.

Requested changes

1- no changes

  • validity: top
  • significance: top
  • originality: top
  • clarity: top
  • formatting: perfect
  • grammar: excellent

Login to report


Comments

Pierfrancesco Urbani  on 2017-04-19  [id 118]

We warmly thank our referee: we could not agree more with her/his report.