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

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

Résultats de recherche: Contribution à un journal › Article de conférence › Revue par des pairs

Résumé

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.

langue originale	Anglais
Pages (de - à)	381-394
Nombre de pages	14
journal	Physica A: Statistical Mechanics and its Applications
Volume	306
Les DOIs	https://doi.org/10.1016/S0378-4371(02)00516-2
état	Publié - 1 avr. 2002
Modification externe	Oui
Evénement	21th IUPAP Conference on Invited Papares (STATPHYS 21) - Cancun, Mexique Durée: 15 juil. 2001 → 21 juil. 2001

Accès au document

10.1016/S0378-4371(02)00516-2

Contient cette citation

@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",

}

Phase transitions and complexity in computer science: An overview of the statistical physics approach to the random satisfiability problem. / Biroli, Giulio; Cocco, Simona; Monasson, Rémi.
Dans: Physica A: Statistical Mechanics and its Applications, Vol 306, 01.04.2002, p. 381-394.

Résultats de recherche: Contribution à un journal › Article de conférence › Revue par des pairs

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

Résumé

Accès au document

Empreinte digitale

Contient cette citation