Phase transitions and complexity in computer science: An overview of the statistical physics approach to the random satisfiability problem

Giulio Biroli; Simona Cocco; Rémi Monasson

doi:10.1016/S0378-4371(02)00516-2

Phase transitions and complexity in computer science: An overview of the statistical physics approach to the random satisfiability problem

Giulio Biroli
, Simona Cocco
, Rémi Monasson

Department of Physics and Astronomy
Rutgers University–New Brunswick
Department of Physics
University of Illinois at Chicago
Center for Atomic-scale Materials Physics (CAMP)
University of Chicago

Research output: Contribution to journal › Conference article › peer-review

21 Citations (Scopus)

Abstract

Phase transitions, ubiquitous in condensed matter physics, are encountered in computer science too. The existence of critical phenomena has deep consequences on computational complexity, that is the resolution times of various optimization or decision problems. Concepts and methods borrowed from the statistical physics of disordered and out-of-equilibrium systems shed new light on the dynamical operation of solving algorithms.

Original language	English
Pages (from-to)	381-394
Number of pages	14
Journal	Physica A: Statistical Mechanics and its Applications
Volume	306
DOIs	https://doi.org/10.1016/S0378-4371(02)00516-2
Publication status	Published - 1 Apr 2002
Externally published	Yes
Event	21th IUPAP Conference on Invited Papares (STATPHYS 21) - Cancun, Mexico Duration: 15 Jul 2001 → 21 Jul 2001

Keywords

Analysis of algorithm
Optimization
Phase transitions
Satisfiability
Statistical physics

Access to Document

10.1016/S0378-4371(02)00516-2

Cite this

@article{be9af7f66338488c9b73a98de1c3b24a,

title = "Phase transitions and complexity in computer science: An overview of the statistical physics approach to the random satisfiability problem",

abstract = "Phase transitions, ubiquitous in condensed matter physics, are encountered in computer science too. The existence of critical phenomena has deep consequences on computational complexity, that is the resolution times of various optimization or decision problems. Concepts and methods borrowed from the statistical physics of disordered and out-of-equilibrium systems shed new light on the dynamical operation of solving algorithms.",

keywords = "Analysis of algorithm, Optimization, Phase transitions, Satisfiability, Statistical physics",

author = "Giulio Biroli and Simona Cocco and R{\'e}mi Monasson",

year = "2002",

month = apr,

day = "1",

doi = "10.1016/S0378-4371(02)00516-2",

language = "English",

volume = "306",

pages = "381--394",

journal = "Physica A: Statistical Mechanics and its Applications",

issn = "0378-4371",

publisher = "Elsevier B.V.",

note = "21th IUPAP Conference on Invited Papares (STATPHYS 21) ; Conference date: 15-07-2001 Through 21-07-2001",

}

TY - JOUR

T1 - Phase transitions and complexity in computer science

T2 - 21th IUPAP Conference on Invited Papares (STATPHYS 21)

AU - Biroli, Giulio

AU - Cocco, Simona

AU - Monasson, Rémi

PY - 2002/4/1

Y1 - 2002/4/1

N2 - Phase transitions, ubiquitous in condensed matter physics, are encountered in computer science too. The existence of critical phenomena has deep consequences on computational complexity, that is the resolution times of various optimization or decision problems. Concepts and methods borrowed from the statistical physics of disordered and out-of-equilibrium systems shed new light on the dynamical operation of solving algorithms.

AB - Phase transitions, ubiquitous in condensed matter physics, are encountered in computer science too. The existence of critical phenomena has deep consequences on computational complexity, that is the resolution times of various optimization or decision problems. Concepts and methods borrowed from the statistical physics of disordered and out-of-equilibrium systems shed new light on the dynamical operation of solving algorithms.

KW - Analysis of algorithm

KW - Optimization

KW - Phase transitions

KW - Satisfiability

KW - Statistical physics

U2 - 10.1016/S0378-4371(02)00516-2

DO - 10.1016/S0378-4371(02)00516-2

M3 - Conference article

AN - SCOPUS:0036540557

SN - 0378-4371

VL - 306

SP - 381

EP - 394

JO - Physica A: Statistical Mechanics and its Applications

JF - Physica A: Statistical Mechanics and its Applications

Y2 - 15 July 2001 through 21 July 2001

ER -

Phase transitions and complexity in computer science: An overview of the statistical physics approach to the random satisfiability problem

Abstract

Keywords

Access to Document

Fingerprint

Cite this