CODEWITHSUNDEEP
algorithm
user182513
user182513

Reputation:

looking for 3-SAT special cases

I'm looking for 3-SAT special cases which are solved in Polynomial time and their algorithms. any links?

Thanks.

Upvotes: 2

Views: 874

Answers (2)

Aryabhatta
Aryabhatta

Reputation:

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.

Upvotes: 4

Ulrich Schwarz
Ulrich Schwarz

Reputation: 7727

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.

Upvotes: 1

Related Questions