For a number of random constraint satisfaction problems, such as random k-SAT and random graph/hypergraph coloring, there are very good estimates of the largest constraint density for which solutions exist. Yet, all known polynomial-time algorithms for these problems fail to find solutions even at much lower densities. To understand the origin of this gap we study how the structure of the space of solutions evolves in such problems as constraints are added. In particular, we prove that much before solutions disappear, they organize into an exponential number of clusters, each of which is relatively small and far apart from all other clusters. Moreover, inside each cluster most variables are frozen, i.e., take only one value. The existence of such frozen variables gives a satisfying intuitive explanation for the failure of the polynomial-time algorithms analyzed so far. At the same time, our results establish rigorously one of the two main hypotheses underlying Survey Propagation, a heuristic introduced by physicists in recent years that appears to perform extraordinarily well on random constraint satisfaction problems. Copyright 2006 ACM.

On the Solution-Space Geometry of Random Constraint Satisfaction Problems / Achlioptas, D; RICCI TERSENGHI, Federico. - 2006:(2006), pp. 130-139. (Intervento presentato al convegno 38th ACM Symposium on Theory of Computing tenutosi a Seattle; United States nel 21-23 maggio 2006) [10.1145/1132516.1132537].

On the Solution-Space Geometry of Random Constraint Satisfaction Problems

RICCI TERSENGHI, Federico
2006

Abstract

For a number of random constraint satisfaction problems, such as random k-SAT and random graph/hypergraph coloring, there are very good estimates of the largest constraint density for which solutions exist. Yet, all known polynomial-time algorithms for these problems fail to find solutions even at much lower densities. To understand the origin of this gap we study how the structure of the space of solutions evolves in such problems as constraints are added. In particular, we prove that much before solutions disappear, they organize into an exponential number of clusters, each of which is relatively small and far apart from all other clusters. Moreover, inside each cluster most variables are frozen, i.e., take only one value. The existence of such frozen variables gives a satisfying intuitive explanation for the failure of the polynomial-time algorithms analyzed so far. At the same time, our results establish rigorously one of the two main hypotheses underlying Survey Propagation, a heuristic introduced by physicists in recent years that appears to perform extraordinarily well on random constraint satisfaction problems. Copyright 2006 ACM.
2006
38th ACM Symposium on Theory of Computing
Random formulas; Satisfiability; Survey Propagation
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
On the Solution-Space Geometry of Random Constraint Satisfaction Problems / Achlioptas, D; RICCI TERSENGHI, Federico. - 2006:(2006), pp. 130-139. (Intervento presentato al convegno 38th ACM Symposium on Theory of Computing tenutosi a Seattle; United States nel 21-23 maggio 2006) [10.1145/1132516.1132537].
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/208196
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 104
  • ???jsp.display-item.citation.isi??? ND
social impact