Random constraint satisfaction problems

Random constraint satisfaction problems:
a point of view from physics
Guilhem Semerjian
LPT-ENS
29.01.2014 / IAS
Guilhem Semerjian (LPT-ENS)
29.01.2014 / IAS
1 / 22
Outline
1
Constraint satisfaction problems
2
Random ensembles of CSP
3
Statistical physics approach and results
Guilhem Semerjian (LPT-ENS)
29.01.2014 / IAS
2 / 22
Constraint satisfaction problems : definitions
x = (x1 , . . . , xn ) ∈ X n discrete alphabet X
(
1 satisfied
m constraints ψa ({xi }i∈∂a ) =
0 unsatisfied
n variables
solutions
S = {x : ψa (x ∂a ) = 1 ∀a}
Guilhem Semerjian (LPT-ENS)
29.01.2014 / IAS
3 / 22
Constraint satisfaction problems : examples
X = {1, . . . , q} ,
ψa (xi , xj ) = 11(xi 6= xj )
on the edges a = hi, ji of a graph
q-coloring problem
X = {True, False} ,
ψa depends on k variables xia1 , . . . , xiak
ψa = 11(zia1 ∨ · · · ∨ zia1 = True) ,
with zi ∈ {xi , x i }
k -satisfiability problem
ψa = 11(xia1 ⊕ · · · ⊕ xiak = ya ),
with ya ∈ {True, False}
k -xor-satisfiability problem
Guilhem Semerjian (LPT-ENS)
29.01.2014 / IAS
4 / 22
Constraint satisfaction problems
For a given instance (formula/graph), several questions :
decision problem,
is |S| > 0 ? (said satisfiable if yes)
counting problem,
what is |S| ?
optimization problem,
P
what is max
ψa (x) ?
x
a
Worst-case complexity of the decision problem:
k -xor-satisfiability easy (P) for all k
k -satisfiability, q-coloring difficult (NP-complete) for k , q ≥ 3
Guilhem Semerjian (LPT-ENS)
29.01.2014 / IAS
5 / 22
Random constraint satisfaction problems
What about their “typical case” complexities ?
“typical”= with high probability in some random ensemble of instances
Examples :
coloring Erdös-Rényi random graphs G(n, m) choose m edges uniformly at random in the n2 possible ones
random (xor)satisfiability ensembles
choose m hyperedges (k -uplets of variables), among
n
k
Most interesting regime : n, m → ∞ with α = m/n fixed
Guilhem Semerjian (LPT-ENS)
29.01.2014 / IAS
6 / 22
Random constraint satisfaction problems
Pn,α = P[random problem with n variables and
m = αn constraints is satisfiable]
Obvious observations :
Pn,α decreases with α
lim Pn,α = 0 for α large enough
n→∞
First moment proof (for k -sat) :
"
Pn,α = P[|S| ≥ 1] ≤ E[|S|] =
X
x
E
m
Y
#
ψa (x)
a=1
1 αn
n
= 2 1− k
→0
2
for α > αub (k ) = 2k ln 2
Guilhem Semerjian (LPT-ENS)
29.01.2014 / IAS
7 / 22
Random constraint satisfaction problems
“Experimental” observation : phase transition for 1 − Pn,α
associated to a peak in the hardness of solving
Guilhem Semerjian (LPT-ENS)
29.01.2014 / IAS
8 / 22
Random constraint satisfaction problems
Phase transition conjecture : ∃ αs (k ) such that
(
1 if α < αs (k )
lim Pn,α =
n→∞
0 if α > αs (k )
Weaker version proven : ∃ αs (k , n) such that
lim Pn,(1−)αs (k ,n) = 1 ,
n→∞
[Friedgut]
lim Pn,(1+)αs (k ,n) = 0
n→∞
Early rigorous results for random k -satisfiability and q-coloring :
upper and lower bounds on αs (k )
[Chao-Franco, Frieze-Suen, Achlioptas, Dubois, Boufkhad...]
asymptotics of αs (k ) at large k
αs (k ) ≥ 2k ln 2 − k
Guilhem Semerjian (LPT-ENS)
ln 2
+ O(1)
2
[Achlioptas, Moore, Naor, Peres]
[Achlioptas, Peres (04)]
29.01.2014 / IAS
9 / 22
Random constraint satisfaction problems
But :
no precise value of αs (k ) for small k
unsatisfactory understanding of algorithmic difficulty at α < αs (k )
Guilhem Semerjian (LPT-ENS)
29.01.2014 / IAS
10 / 22
Why physics ?
Statistical mechanics :
configuration space x = (x1 , . . . , xn )
energy function E(x)
temperature T
Gibbs-Boltzmann distribution µ(x) = exp[−E(x)/T ]/Z
Low-temperature statistical physics ≈ combinatorial optimization
randomness in the distribution of instances ≈ disordered systems
(spin glasses)
random graphs → mean-field diluted spin glasses
graph coloring corresponds to antiferromagnetic Potts model
Guilhem Semerjian (LPT-ENS)
29.01.2014 / IAS
11 / 22
Outcomes of the physics approach
quantitative estimation of αs (k )
refined picture of the satisfiable phase
analysis of known algorithms
suggestion of new ones
Guilhem Semerjian (LPT-ENS)
29.01.2014 / IAS
12 / 22
Refined picture of the satisfiable phase
Exponential number of solutions for α < αs ,
∼ exp[ns(α)]
Clustering transition at another threshold αd < αs :
apparition of an exponential number of clusters (∼ exp[nΣ(α)]),
each containing an exponential number of solutions (∼ exp[nsint (α)])
at αs cancellation of Σ(α), not of s(α)
Guilhem Semerjian (LPT-ENS)
29.01.2014 / IAS
13 / 22
Refined picture of the satisfiable phase
Can be proven rigorously for random xorsat
[Creignou, Daudé]
[Cocco, Dubois, Mandler, Monasson]
[Mézard, Ricci-Tersenghi, Zecchina]
At αd , apparition of a 2-core in the hypergraph
s(α) = Σ(α) + sint (α)
Σ(αs ) = 0
[more complicated picture for sat and col]
Guilhem Semerjian (LPT-ENS)
29.01.2014 / IAS
14 / 22
Methods
If the formula F has solutions,
define µ(x) =
1
Z
Q
ψa (x ∂a ) uniform measure on S
x1
Factor graph representation
of a formula :
x3
x2
a
c
x8
b
x7
x4
x5
d
x6
Crucial property : in the n, m → ∞ limit with α = m/n fixed
local convergence of the factor graph to a random Galton-Watson tree
Guilhem Semerjian (LPT-ENS)
29.01.2014 / IAS
15 / 22
Methods
For a tree factor graph µ(x) is a rather simple object
(Belief Propagation is exact)
All marginal probabilities can be
easily computed recursively :
Sparse random graphs converge locally to trees
Is it enough for their µ(x) to converge locally to the measure on the
associated tree ?
It depends... (on the correlations decay)
Guilhem Semerjian (LPT-ENS)
29.01.2014 / IAS
16 / 22
Methods
Yes in “replica symmetric” cases
Ferromagnetic Ising models
Matchings
Random CSP for α < αd
[Dembo, Montanari]
[Bordenave, Lelarge, Salez]
Removing a finite subtree, the variables at the boundary are
asymptotically independent
Allows to compute in particular
Guilhem Semerjian (LPT-ENS)
lim n1 log Z
entropy of solutions
29.01.2014 / IAS
17 / 22
Methods
No in presence of “replica symmetry breaking”
(αd < α < αs )
Configuration space partitioned in clusters ⇒ long-range
correlations
Removing a finite subtree, the variables at the boundary remains
correlated, self-consistent ansatz on these boundary conditions
With µ(x) =
P
wc µc (x), each µc has short-range correlations,
c
can be treated as above
Properties of wc encode the value of Σ(α), hence allows the
computation of αs
Guilhem Semerjian (LPT-ENS)
29.01.2014 / IAS
18 / 22
Clustering for k -sat and q-col
Further “condensation” transition :
exponential number of clusters only for α ∈ [αd , αc ]
In general αc < αs , for XORSAT they coincide
Guilhem Semerjian (LPT-ENS)
29.01.2014 / IAS
19 / 22
Recent rigorous results
Physical intuition and heuristic results turned into rigorous proofs
Existence of clusters and frozen variables
[Achlioptas, Molloy]
Improved bounds on αs (k ) at large k
3 ln 2
+ o(1) [Coja-Oghlan, Panagiotou (12)]
2
1 + ln 2
αs (k ) = 2k ln 2 −
+ o(1)
[Coja-Oghlan (14)]
2
αs (k ) ≥ 2k ln 2 −
independence number of d-regular graphs for large (but finite) d
[Ding, Sly, Sun (13)]
Guilhem Semerjian (LPT-ENS)
29.01.2014 / IAS
20 / 22
Perspectives
Schemes of rigorous proofs:
Large k , q results, of combinatorics nature
[Achlioptas, Coja-Oghlan]
Interpolation method, originally devised for the
Sherrington-Kirkpatrick model
[Guerra, Toninelli, Aizenman, Talagrand, Panchenko]
Local convergence approach
[Aldous]
done for sparse random graphs in the “replica symmetric” regime
open problem in the “replica symmetry breaking” regime
Guilhem Semerjian (LPT-ENS)
29.01.2014 / IAS
21 / 22
Short bibliography
M. Mézard, G. Parisi and R. Zecchina,
Science 297, 812 (2002)
S. Mertens, M. Mézard and R. Zecchina,
Random Struct. Alg. 28, 340 (2006)
F. Krzakala, A. Montanari, F. Ricci-Tersenghi, G. Semerjian and
L. Zdeborova, PNAS 104, 10318 (2007)
F. Altarelli, R. Monasson, G. Semerjian and F. Zamponi,
in Handbook of Satisfiability, IOS press (2009), arxiv:0802.1829
M. Mézard and A. Montanari,
Information, Physics, and Computation, OUP (2009)
Guilhem Semerjian (LPT-ENS)
29.01.2014 / IAS
22 / 22

Download Report