overview of phase transitions in constraint satisfaction

# Frontiers in Problem Solving:

Phase Transitions and Complexity

Special issue of *Artificial Intelligence*, edited by T. Hogg, B. A. Huberman and C. Williams, 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.