Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!cs.utexas.edu!sdd.hp.com!elroy.jpl.nasa.gov!ucla-cs!rachel@lanai.cs.ucla.edu
From: rachel@lanai.cs.ucla.edu (Rachel Ben-Eliyahu)
Newsgroups: comp.theory
Subject: wanted : tractable satisfiability
Message-ID: <38877@shemp.CS.UCLA.EDU>
Date: 11 Sep 90 20:22:41 GMT
Sender: news@CS.UCLA.EDU
Distribution: usa
Organization: UCLA Computer Science Department
Lines: 14


It is known that to decide whether a set of sentences in propositional
logic is satisfiable is NP-complete. However, there are 
polynomial time algorithms for deciding the satisfiability of a set
of horn clauses and a set of clauses which do not contain
more then 2 literals.

Does anyone know of other subsets of propositional logic that
their satisfiability can be decided in polynomial time ??
References will be appreciated.

Thank You

Rachel.