Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!cs.utexas.edu!uunet!mcsun!tuvie!vexpert.dbai.tuwien.ac.at!gottlob
From: gottlob@vexpert.dbai.tuwien.ac.at (Georg Gottlob)
Newsgroups: comp.theory
Subject: question on restrictions of SAT
Keywords: satisfiability complexity
Message-ID: <3825@vexpert.dbai.tuwien.ac.at>
Date: 6 Jan 91 11:09:48 GMT
Organization: DB and ES Subdivision, TU Vienna
Lines: 23



The satisfiability problem (SAT) and many restricted versions of 
it (e.g. monotone SAT, planar SAT etc.) remain NP-complete 
even if |c|<=3 for each clause c in the problem instances.

I am looking for restricted versions of SAT (defined by 
additional syntactic conditions on the problem instances) 
such that:


  1) the restricted version is still NP-complete, and
  
  2) the restricted version is solvable in polynomial time 
     if the cardinality of clauses id bounded by a constant k,
     i.e., |c|<=k for each clause c in the problem instance.

Examples of such classes and/or pointers to relevant references
are welcome.

--------------------------
Georg Gottlob  
gottlob@vexpert.dbai.tuwien.ac.at