---
title: "Stochastic Search and Phase Transitions: AI Meets Physics"
authors:
  - "Bart Selman"
doi: ""
url: "https://ijcai.org/proceedings/1995/130"
pdf: "https://ijcai.org/proceedings/1995/0130.pdf"
venue: "Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence"
year: 1995
pages: "998-1001"
track: "Invited Speakers"
keywords:
---

# Stochastic Search and Phase Transitions: AI Meets Physics

Bart Selman

*Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence*, pages 998-1001.

## 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.