Facing Comutational Challenges in AI:
     Stochastic Search and Reasoning Strategies

                           Bart Selman
                         AT&T Laboratories
                       Murray Hill, NJ 07974


      Significant progress has been made recently in our understanding 
      of the nature of computationally hard search and reasoning problems 
      in AI. In addition, new stochastic methods have been discovered 
      for solving such problems. I'll discuss these developments and also 
      a surprising connection to phase transition phenomena studied 
      in physics.