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

DOI10.1016/S0378-4371(02)00516-2zbMath0994.68071MaRDI QIDQ1596668

Simona Cocco, Giulio Biroli, Remi Monasson

Publication date: 2 May 2002

Published in: Physica A (Search for Journal in Brave)

zbMATH Keywords

critical phenomenaout-of-equilibrium systemsresolution times

Mathematics Subject Classification ID

Descriptive complexity and finite models (68Q19)

Related Items (1)

Correlations between Horn fractions, satisfiability and solver performance for fixed density random 3-CNF instances

Cites Work

• Unnamed Item
• Unnamed Item
• Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
• Entropy of theK-Satisfiability Problem
• Determining computational complexity from characteristic ‘phase transitions’
• Statistical mechanics methods and phase transitions in optimization problems

This page was built for publication: Phase transitions and complexity in computer science: An overview of the statistical physics approach to the random satisfiability problem