SAT: references on satisfiability

collected by

Phase transition behaviour

Phase Transitions and the Search Problem
T. Hogg, B. A. Huberman and C. Williams, Tutorial paper. 1996.

The Constrainedness of Search.
Ian Gent, Ewan MacIntyre, Patrick Prosser, and Toby Walsh. Proceedings of AAAI-96, pages 246-252, 1996.

Hard and Easy Distribution of SAT Problems
David Mitchell, Bart Selman, and Hector Levesque, Proceedings AAAI-92.

The SAT Phase Transition
Ian Gent and Toby Walsh. Proceedings of ECAI-94, ed. A G Cohn, John Wiley & Sons, pages 105-109, 1994.

The Satisfiability Constraint Gap.
Ian Gent and Toby Walsh. Artificial Intelligence, 81 (1-2), 1996.

A Better Upper Bound for the Unsatisfiability Threshold.
L. M. Kirousis, E. Kranakis, D. Krizanc. Technical report TR-96-09, School of Computer Science, Carleton University, 196.

Easy Problems are Sometimes Hard.
Ian Gent and Toby Walsh. Artificial Intelligence, 70, 335-345, 1994.

Local Search and the Number of Solutions.
Dave Clark, Jeremy Frank, Ian Gent, Ewan MacIntyre, Neven Tomov and Toby Walsh. Proceedings of CP-96, 1996.

Tuning Local Search for Satisfiability Testing
A. J. Parkes and J. Walser, Proceedings of the 13th National Conference on Artificial Intelligence, Portland, OR, 1996.