Stochastic Search and Phase Transitions: AI Meets Physics
Abstract
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.
Cite
Text
Selman. "Stochastic Search and Phase Transitions: AI Meets Physics." International Joint Conference on Artificial Intelligence, 1995.Markdown
[Selman. "Stochastic Search and Phase Transitions: AI Meets Physics." International Joint Conference on Artificial Intelligence, 1995.](https://mlanthology.org/ijcai/1995/selman1995ijcai-stochastic/)BibTeX
@inproceedings{selman1995ijcai-stochastic,
title = {{Stochastic Search and Phase Transitions: AI Meets Physics}},
author = {Selman, Bart},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {1995},
pages = {998-1002},
url = {https://mlanthology.org/ijcai/1995/selman1995ijcai-stochastic/}
}