Stochastic Search And Phase Transitions: AI Meets Physics Bart Selman AT&T Bell Laboratories Murray Hill, N.J. USA
Computational Challenges In AI
A Few Examples
Complexity Results, Cont.
What Is The Impact Of These Results?
PPT Slide
Recent Developments
Overview
PART A. Computationally Hard Instances
Satisfiability
Some Example Applications Of SAT
Average-Case Analysis
Aside: Small Hard Instances Do Exist!
The Instance
Generating Hard Random Formulas
Intuition
Theoretical Status Of Threshold
The Physics Of Thresholds
Summary Phase Transition Effect
PART B. Fast Stochastic Methods
Standard Procedures For SAT
Randomized Greedy Local Search: GSAT
How Well Does It Work?
Improvements Of Basic Local Search
Simulated Annealing
Random Walk
Biased Random Walk
Experimental Results: Hard Random 3SAT
Other Applications Of GSAT
Showing UNSAT / Inconsistencies
Length Of Proofs
Limitations Of Resolution
Stochastic Search For Proofs
Recap Of Results
Impact And Future Directions
Impact, Cont.
Some Challenges
Email: selman@cs.cornell.edu
Home Page: www.cs.cornell.edu/home/selman
Download presentation source