Rigorous location of phase transitions in hard optimization problems

Dimitris Achlioptas (), Assaf Naor and Yuval Peres
Additional contact information
Dimitris Achlioptas: Microsoft Research, One Microsoft Way
Assaf Naor: Microsoft Research, One Microsoft Way
Yuval Peres: University of California

Nature, 2005, vol. 435, issue 7043, 759-764

Abstract: 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.

Date: 2005
References: Add references at CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
https://www.nature.com/articles/nature03602 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:nat:nature:v:435:y:2005:i:7043:d:10.1038_nature03602

Ordering information: This journal article can be ordered from
https://www.nature.com/

DOI: 10.1038/nature03602

Access Statistics for this article

Nature is currently edited by Magdalena Skipper

More articles in Nature from Nature
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().