Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!know!zaphod.mps.ohio-state.edu!wuarchive!julius.cs.uiuc.edu!ux1.cso.uiuc.edu!ux1.cso.uiuc.edu!m.cs.uiuc.edu!gillies
From: gillies@m.cs.uiuc.edu
Newsgroups: comp.theory
Subject: Re: wanted : tractable satisfiability
Message-ID: <37800009@m.cs.uiuc.edu>
Date: 12 Sep 90 03:24:00 GMT
References: <38877@shemp.CS.UCLA.EDU>
Lines: 12
Nf-ID: #R:shemp.CS.UCLA.EDU:38877:m.cs.uiuc.edu:37800009:000:439
Nf-From: m.cs.uiuc.edu!gillies    Sep 11 22:24:00 1990


Here is a paper with an exact characterization of the types of boolean
clauses that can be satisfied in polynomial time, and the types of
boolean clauses that are NP-complete to satisfy:

10th ACM STOC (Symposium on Theory of Computing)
Thomas J. Schaefer*
"The complexity of satisfiability problems"
pp 216-226

This paper is a bear to read (unless you're a logician, which I'm
not).  But I did get through it once, for a term project 8-)