SAT: references on satisfiability

collected by Ian P. Gent
ipg@cs.strath.ac.uk
Toby Walsh
tw@cs.strath.ac.uk

Phase transition behaviour

General studies

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.

Random 3SAT

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.

Constant probability

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

Search cost

Stochastic Local Search - Methods, Models, Applications
Holger Hoos, PhD thesis, TU Darmstadt, 1998.

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.