Universality of the SAT-UNSAT (jamming) threshold in non-convex continuous constraint satisfaction problems. Franz, S., Parisi, G., Sevelev, M., Urbani, P., & Zamponi, F. SCIPOST PHYSICS, MAY-JUN, 2017. doi abstract bibtex 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.
@article{ ISI:000410372200004,
Author = {Franz, Silvio and Parisi, Giorgio and Sevelev, Maksim and Urbani,
Pierfrancesco and Zamponi, Francesco},
Title = {{Universality of the SAT-UNSAT (jamming) threshold in non-convex
continuous constraint satisfaction problems}},
Journal = {{SCIPOST PHYSICS}},
Year = {{2017}},
Volume = {{2}},
Number = {{3}},
Month = {{MAY-JUN}},
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.}},
DOI = {{10.21468/SciPostPhys.2.3.019}},
Article-Number = {{UNSP 019}},
ISSN = {{2542-4653}},
ResearcherID-Numbers = {{Franz, Silvio/B-2137-2019
}},
ORCID-Numbers = {{Franz, Silvio/0000-0001-8300-8443
Sevelev, Maxime/0000-0001-9966-6408}},
Unique-ID = {{ISI:000410372200004}},
}
Downloads: 0
{"_id":"zLsW4Txp25p4LZma2","bibbaseid":"franz-parisi-sevelev-urbani-zamponi-universalityofthesatunsatjammingthresholdinnonconvexcontinuousconstraintsatisfactionproblems-2017","authorIDs":[],"author_short":["Franz, S.","Parisi, G.","Sevelev, M.","Urbani, P.","Zamponi, F."],"bibdata":{"bibtype":"article","type":"article","author":[{"propositions":[],"lastnames":["Franz"],"firstnames":["Silvio"],"suffixes":[]},{"propositions":[],"lastnames":["Parisi"],"firstnames":["Giorgio"],"suffixes":[]},{"propositions":[],"lastnames":["Sevelev"],"firstnames":["Maksim"],"suffixes":[]},{"propositions":[],"lastnames":["Urbani"],"firstnames":["Pierfrancesco"],"suffixes":[]},{"propositions":[],"lastnames":["Zamponi"],"firstnames":["Francesco"],"suffixes":[]}],"title":"Universality of the SAT-UNSAT (jamming) threshold in non-convex continuous constraint satisfaction problems","journal":"SCIPOST PHYSICS","year":"2017","volume":"2","number":"3","month":"MAY-JUN","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.","doi":"10.21468/SciPostPhys.2.3.019","article-number":"UNSP 019","issn":"2542-4653","researcherid-numbers":"Franz, Silvio/B-2137-2019 ","orcid-numbers":"Franz, Silvio/0000-0001-8300-8443 Sevelev, Maxime/0000-0001-9966-6408","unique-id":"ISI:000410372200004","bibtex":"@article{ ISI:000410372200004,\nAuthor = {Franz, Silvio and Parisi, Giorgio and Sevelev, Maksim and Urbani,\n Pierfrancesco and Zamponi, Francesco},\nTitle = {{Universality of the SAT-UNSAT (jamming) threshold in non-convex\n continuous constraint satisfaction problems}},\nJournal = {{SCIPOST PHYSICS}},\nYear = {{2017}},\nVolume = {{2}},\nNumber = {{3}},\nMonth = {{MAY-JUN}},\nAbstract = {{Random constraint satisfaction problems (CSP) have been studied\n extensively using statistical physics techniques. They provide a\n benchmark to study average case scenarios instead of the worst case one.\n The interplay between statistical physics of disordered systems and\n computer science has brought new light into the realm of computational\n complexity theory, by introducing the notion of clustering of solutions,\n related to replica symmetry breaking. However, the class of problems in\n which clustering has been studied often involve discrete degrees of\n freedom: standard random CSPs are random K-SAT (aka disordered Ising\n models) or random coloring problems (aka disordered Potts models). In\n this work we consider instead problems that involve continuous degrees\n of freedom. The simplest prototype of these problems is the perceptron.\n Here we discuss in detail the full phase diagram of the model. In the\n regions of parameter space where the problem is non-convex, leading to\n multiple disconnected clusters of solutions, the solution is critical at\n the SAT / UNSAT threshold and lies in the same universality class of the\n jamming transition of soft spheres. We show how the critical behavior at\n the satisfiability threshold emerges, and we compute the critical\n exponents associated to the approach to the transition from both the SAT\n and UNSAT phase. We conjecture that there is a large universality class\n of non-convex continuous CSPs whose SAT-UNSAT threshold is described by\n the same scaling solution.}},\nDOI = {{10.21468/SciPostPhys.2.3.019}},\nArticle-Number = {{UNSP 019}},\nISSN = {{2542-4653}},\nResearcherID-Numbers = {{Franz, Silvio/B-2137-2019\n }},\nORCID-Numbers = {{Franz, Silvio/0000-0001-8300-8443\n Sevelev, Maxime/0000-0001-9966-6408}},\nUnique-ID = {{ISI:000410372200004}},\n}\n\n","author_short":["Franz, S.","Parisi, G.","Sevelev, M.","Urbani, P.","Zamponi, F."],"key":"ISI:000410372200004","id":"ISI:000410372200004","bibbaseid":"franz-parisi-sevelev-urbani-zamponi-universalityofthesatunsatjammingthresholdinnonconvexcontinuousconstraintsatisfactionproblems-2017","role":"author","urls":{},"downloads":0},"bibtype":"article","biburl":"http://nanotec.cnr.it/data/nanotec/nanotec-with-abstract.bib","creationDate":"2020-04-21T16:04:30.682Z","downloads":0,"keywords":[],"search_terms":["universality","sat","unsat","jamming","threshold","non","convex","continuous","constraint","satisfaction","problems","franz","parisi","sevelev","urbani","zamponi"],"title":"Universality of the SAT-UNSAT (jamming) threshold in non-convex continuous constraint satisfaction problems","year":2017,"dataSources":["qabHv7MDBiEn82jCu"]}