Frontiers in Problem Solving:
Phase Transitions and Complexity

This special issue of Artificial Intelligence is edited by T. Hogg, B. A. Huberman and C. Williams and appears as volume 81, issue 1-2 (March 1996).

Contents:

• T. Hogg, B. A. Huberman and C. Williams, Phase Transitions and the Search Problem, pp. 1--15.
  (an introduction to the special issue)
• B. Selman, D. Mitchell and H. J. Levesque, Generating Hard Satisfiability Problems, pp. 17--29.
• J. M. Crawford and L. D. Auton, Experimental Results on the Crossover Point in Random 3SAT, pp. 31-57.
• I. P. Gent and T. Walsh, The Satisfiability Constraint Gap, pp. 59-80.
• P. Prosser, An Empirical Study of Phase Transitions in Binary Constraint Satisfaction Problems, pp. 81-109.
• D. G. Mitchell and H. J. Levesque, Some Pitfalls for Experimenters with Random SAT, pp. 111-125.
• T. Hogg, Refining the Phase Transition in Combinatorial Search, pp. 127-154.
• B. M. Smith and M. E. Dyer, Locating the Phase Transition in Binary Constraint Satisfaction Problems, pp. 155-181.
• J. W. Freeman, Hard Random 3-SAT Problems and the Davis-Putnam Procedure, pp. 183-198.
• R. Schrag and J. M. Crawford, Implicates and Prime Implicates in Random 3SAT, pp. 199-222.
• W. Zhang and R. E. Korf, A Study of Complexity Transitions on the Asymmetric Traveling Salesman Problem, pp. 223-239.
• T. Bylander, A Probabilistic Analysis of Propositional STRIPS Planning, pp. 241-271.
• B. Selman and S. Kirkpatrick, Critical Behavior in the Computational Cost of Satisfiability Testing, pp. 273-295.
• J. C. Pemberton and W. Zhang, Epsilon-Transformation: Exploiting Phase Transitions to Solve Combinatorial Optimization Problems, pp. 297-325.
• S. H. Clearwater and T. Hogg, Problem Structure Heuristics and Scaling Behavior for Genetic Algorithms, pp. 327-347.