Stochastic Search And Phase Transitions: AI Meets PhysicsBart Selman AT&T Bell LaboratoriesMurray Hill, N.J. USA

Stochastic Search And Phase Transitions: AI Meets Physics

Computational Challenges In AI

A Few Examples

Complexity Results, Cont.

What Is The Impact Of These Results?

Recent Developments

Overview

PART A. Computationally Hard Instances

Satisfiability

Some Example Applications Of SAT

PP Presentation

Average-Case Analysis

PP Presentation

PP Presentation

Aside: Small Hard Instances Do Exist!

The Instance

Generating Hard Random Formulas

PP Presentation

Intuition

PP Presentation

Theoretical Status Of Threshold

PP Presentation

The Physics Of Thresholds

PP Presentation

PP Presentation

Summary Phase Transition Effect

PP Presentation

PART B. Fast Stochastic Methods

Standard Procedures For SAT

PP Presentation

PP Presentation

Randomized Greedy Local Search: GSAT

How Well Does It Work?

PP Presentation

PP Presentation

Improvements Of Basic Local Search

Simulated Annealing

Random Walk

Biased Random Walk

Experimental Results: Hard Random 3SAT

Other Applications Of GSAT

PP Presentation

PP Presentation

Showing UNSAT / Inconsistencies

PP Presentation

Length Of Proofs

Limitations Of Resolution

Stochastic Search For Proofs

Recap Of Results

PP Presentation

Impact And Future Directions

Impact, Cont.

Some Challenges

PP Presentation