To celebrate 25 yeaxs of research on the satisfiability (SAT) problem, a spe-
special workshop entitled "Satisfiability Problem: Theory and Applications" was held
March 11-13, 1996, at the NSF DIMACS National Research Center. The workshop
was organized by Dingzhu Du, Jun Gu, and Panos Pardalos. David Johnson and
Moshe Vardi were involved in the early planning of the workshop. The Advisory
Committee of the workshop, Bob Johnson, David Johnson, Christos Papadimitriou,
Paul Purdom, and Benjamin Wah, provided suggestions and comments during this
special event.
The satisfiability problem is central in the theory of computation. It is a core
of computationally intractable NP-complete problems. In practice, the SAT prob-
problem is fundamental in solving many application problems in automated reasoning,
computer-aided design, computer-aided manufacturing, machine vision, database,
robotics, scheduling, integrated circuit design, computer architecture design, and
computer networking. Methods to solve the SAT problem play a crucial role in
the development of efficient computing systems. There has been a strong relation-
relationship between the theory, the algorithms, and the applications of the SAT problem.
This workshop brought together a group of distinguished theorists, algorithmists,
and practitioners working on the SAT problem and on its industrial applications,
enhancing the interaction between the three research groups.
from and indus-