The Workshop on "The Satisfiability Problem: Theory and Applications", held
in March 1996, was part of the 1995-1996 DIMACS Special Year on Logic and
Algorithms. We would like to express our appreciation to Dingzhu Du, Jun Gu, and
Panos Pardalos for their efforts in organizing and planning this successful workshop
as well as editing this volume of papers.
The workshop was part of the broader Special Year on Logic and Algorithms
program, which focused on computer-aided verification, finite models, and proof
complexity. The Special Year encouraged collaborations among very different re-
research communities, and this volume records one of many workshops in which this
was achieved. We also extend our thanks to Eric Allender, Robert Kurshan, and
Moshe Vardi for their work over many months as Special Year organizers.
DIMACS gratefully acknowledges the generous support that makes these pro-
programs possible. The National Science Foundation, through its Science and Tech-
Technology Center program; the New Jersey Commission on Science and Technology;
and DIMACS partners at Rutgers, Princeton, AT&T Labs, Bell Labs, and Bellcore
all generously supported the Special Year.