Rigorous location of phase transitions in hard optimization problems

Dimitris Achlioptas, Assaf Naor, Yuval Peres

Research output: Contribution to journalArticle

159 Scopus citations

Abstract

It is widely believed that for many optimization problems, no algorithm is substantially more efficient than exhaustive search. This means that finding optimal solutions for many practical problems is completely beyond any current or projected computational capacity. To understand the origin of this extreme 'hardness', computer scientists, mathematicians and physicists have been investigating for two decades a connection between computational complexity and phase transitions in random instances of constraint satisfaction problems. Here we present a mathematically rigorous method for locating such phase transitions. Our method works by analysing the distribution of distances between pairs of solutions as constraints are added. By identifying critical behaviour in the evolution of this distribution, we can pinpoint the threshold location for a number of problems, including the two most-studied ones: random k-SAT and random graph colouring. Our results prove that the heuristic predictions of statistical physics in this context are essentially correct. Moreover, we establish that random instances of constraint satisfaction problems have solutions well beyond the reach of any analysed algorithm.

Original languageEnglish (US)
Pages (from-to)759-764
Number of pages6
JournalNature
Volume435
Issue number7043
DOIs
StatePublished - Jun 9 2005
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General

Fingerprint Dive into the research topics of 'Rigorous location of phase transitions in hard optimization problems'. Together they form a unique fingerprint.

  • Cite this