looking for 3-SAT special cases

I'm looking for 3-SAT spe开发者_开发知识库cial cases which are solved in Polynomial time and their algorithms. any links?

Thanks.

Read the excellent (but a bit hard to read) paper by Thomas J Schaeffer: The Complexity of Satisfiable Problems which generalizes satisfiability problems to an infinite class of problems like 3SAT, Not all Equal 3Sat etc, and shows that each problem is either in P or NP-Complete.

The paper also determines necessary and sufficient conditions to determine if a particular problem is in P or NP-Complete (called the Dichotomy Theorem).

I suppose you will also find an P time algorithm in there (not very sure) for the problems which are in P.

Hope that helps.

2-SAT is in P (but MAX-2-SAT isn't, funnily enough), I'm not sure about monotone 3-SAT. Almost all occurence restrictions are still NPC.

As always in these matters, Garey/Johnson's Computers and Intractability is your friend.