Determining computational complexity from characteristic ‘phase transitions’

Rémi Monasson, Riccardo Zecchina, Scott Kirkpatrick (), Bart Selman and Lidror Troyansky
Additional contact information
Rémi Monasson: CNRS-Laboratoire de Physique Théorique
Riccardo Zecchina: The Abdus Salam International Centre for Theoretical Physics
Scott Kirkpatrick: IBM, Thomas J. Watson Research Center
Bart Selman: Cornell University
Lidror Troyansky: Institute of Computer Science, The Hebrew University

Nature, 1999, vol. 400, issue 6740, 133-137

Abstract: Abstract Non-deterministic polynomial time (commonly termed ‘NP-complete’) problems are relevant to many computational tasks of practical interest—such as the ‘travelling salesman problem’—but are difficult to solve: the computing time grows exponentially with problem size in the worst case. It has recently been shown that these problems exhibit ‘phase boundaries’, across which dramatic changes occur in the computational difficulty and solution character—the problems become easier to solve away from the boundary. Here we report an analytic solution and experimental investigation of the phase transition in K -satisfiability, an archetypal NP-complete problem. Depending on the input parameters, the computing time may grow exponentially or polynomially with problem size; in the former case, we observe a discontinuous transition, whereas in the latter case a continuous (second-order) transition is found. The nature of these transitions may explain the differing computational costs, and suggests directions for improving the efficiency of search algorithms. Similar types of transition should occur in other combinatorial problems and in glassy or granular materials, thereby strengthening the link between computational models and properties of physical systems.

Date: 1999
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.nature.com/articles/22055 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:400:y:1999:i:6740:d:10.1038_22055

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

DOI: 10.1038/22055

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 ().