For a large number of random constraint satisfaction problems, such as random k-SAT and random graph and hypergraph coloring, there exist very good estimates of the largest constraint density for which solutions exist. All known polynomial-time algorithms for these problems, though, fail to find solutions even at much lower densities. To understand the origin of this gap one can study how the structure of the space of solutions evolves in such problems as constraints are added. In particular, it is known 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. Here we further prove that inside every cluster the vast majority of 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 lend support to 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.

RANDOM FORMULAS HAVE FROZEN VARIABLES / Dimitris, Achlioptas; RICCI TERSENGHI, Federico. - In: SIAM JOURNAL ON COMPUTING. - ISSN 0097-5397. - 39:1(2009), pp. 260-280. (Intervento presentato al convegno 38th Annual ACM Symposium on Theory of Computing tenutosi a Seattle, WA nel MAY 05-23, 2006) [10.1137/070680382].

RANDOM FORMULAS HAVE FROZEN VARIABLES

RICCI TERSENGHI, Federico
2009

Abstract

For a large number of random constraint satisfaction problems, such as random k-SAT and random graph and hypergraph coloring, there exist very good estimates of the largest constraint density for which solutions exist. All known polynomial-time algorithms for these problems, though, fail to find solutions even at much lower densities. To understand the origin of this gap one can study how the structure of the space of solutions evolves in such problems as constraints are added. In particular, it is known 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. Here we further prove that inside every cluster the vast majority of 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 lend support to 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.
2009
frozen variables; phase transitions; random formulas; satisfiability
01 Pubblicazione su rivista::01a Articolo in rivista
RANDOM FORMULAS HAVE FROZEN VARIABLES / Dimitris, Achlioptas; RICCI TERSENGHI, Federico. - In: SIAM JOURNAL ON COMPUTING. - ISSN 0097-5397. - 39:1(2009), pp. 260-280. (Intervento presentato al convegno 38th Annual ACM Symposium on Theory of Computing tenutosi a Seattle, WA nel MAY 05-23, 2006) [10.1137/070680382].
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/131318
 Attenzione

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

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