Table of ContentsStochastic 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 PPT Slide Average-Case Analysis PPT Slide PPT Slide Aside: Small Hard Instances Do Exist! The Instance Generating Hard Random Formulas PPT Slide Intuition PPT Slide Theoretical Status Of Threshold PPT Slide The Physics Of Thresholds PPT Slide PPT Slide Summary Phase Transition Effect PPT Slide PART B. Fast Stochastic Methods Standard Procedures For SAT PPT Slide PPT Slide Randomized Greedy Local Search: GSAT How Well Does It Work? PPT Slide PPT Slide Improvements Of Basic Local Search Simulated Annealing Random Walk Biased Random Walk Experimental Results: Hard Random 3SAT Other Applications Of GSAT PPT Slide PPT Slide Showing UNSAT / Inconsistencies PPT Slide Length Of Proofs Limitations Of Resolution Stochastic Search For Proofs Recap Of Results PPT Slide Impact And Future Directions Impact, Cont. Some Challenges PPT Slide |
Author: Bart Seman/Frank A. (GraphicMods)
Email: selman@cs.cornell.edu Home Page: www.cs.cornell.edu/home/selman |