Theory and Applications of Satisfiability Testing : 7th International Conference, SAT 2004, Vancouver, BC, Canada, May 10-13, 2004, Revised Selected Papers

The 7th International Conference on Theory and Applications of Satis?ab- ity Testing (SAT 2004) was held 10-13 May 2004 in Vancouver, BC, Canada. The conference featured 9 technical paper sessions, 2 poster sessions, as well as the 2004 SAT Solver Competition and the 2004 QBF Solver Evaluation. It also included invited talks by Stephen A. Cook (University of Toronto) and Kenneth McMillan (Cadence Berkeley Labs). The 89 participants represented no less than 17 countries and four continents. SAT 2004 continued the series of meetings which started with the Workshops on Satis?ability held in Siena, Italy (1996), Paderborn, Germany (1998) and Renesse, The Netherlands (2000); the Workshop on Theory and Applications of Satis?ability Testing held in Boston, USA(2001);theSymposiumonTheoryandApplicationsofSatis?abilityTesting held in Cincinnati, USA (2002); and the 6th International Conference on Theory and Applications of Satis?ability Testing held in Santa Margherita Ligure, Italy (2003). The International Conference on Theory and Applications of Satis?ability Testing is the primary annual meeting for researchers studying the propo- tional satis?ability problem (SAT), a prominent problem in both theoretical and applied computer science. SAT lies at the heart of the most important open problem in complexity theory (P vsNP) and underlies many applications in, among other examples, arti?cial intelligence, operations research and electronic design engineering. The primary objective of the conferences is to bring together researchersfromvariousareasandcommunities,includingtheoreticalandexp- imental computer science as well as many relevant application areas, to promote collaboration and the communication of new theoretical and practical results in SAT-related research and its industrial applications.