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

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.

MoreLess

Year of publication:	2002
Authors:	Biroli, Giulio ; Cocco, Simona ; Monasson, Rémi
Published in:	Physica A: Statistical Mechanics and its Applications. - Elsevier, ISSN 0378-4371. - Vol. 306.2002, C, p. 381-394
Publisher:	Elsevier
Subject:	Statistical physics \| Phase transitions \| Optimization \| Satisfiability \| Analysis of algorithm

Online Resource

Check full text access |

More access options

Check Google Scholar

In libraries world-wide (WorldCat)

In German libraries (KVK)

subito order

I need help

More details

Type of publication:	Article
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10010589362