Stochastic search and phase transitions: AI meets physics
Bart Selman · International Joint Conference on Artificial Intelligence · 1995
Computationally hard instances of combinatorial problems arise at a certain critical ratio of constraints to variables. At the critical ratio, problem distributions undergo dramatic changes. I will discuss how an analogous phenomenon occurs in phase transitions studied in physics, and how experiments with critically constrained problems have led to surprising new insights into average-case complexity and stochastic search methods in AI.