I understand 2 SAT can be solved in Polynomial time finding out Strongly Connected Components. What about doing the same for 3SAT?

Question

In case of 3SAT instead of getting 2 implications for one clause, we'd get 12(3C2*2*2) maybe.and which will form a graph of 12m edges when m is the number of clauses in 3 CNF and we can still find out the Strongly Connected Components in that resultant graph. What is wrong in this statement which makes 3 SAT a P problem? eg.

(a+b) = (-a->b).(-b->a)
(a+b+c) = (-a->(b+c)).(-(b+c)->a).....4 more like this
        = (-a ->((-b->c).(-c->b)))....2 for each like this

You are right actually. I just thought after learning these, this must be the first thing to come in a students mind, which must be answered somewhere! — FindersKeeper, Nov 13 '18 at 18:07

score 0 · Accepted Answer · answered Nov 23 '18 at 12:37

Unfortunately, 3-SAT cannot be expressed in 2-SAT, so it cannot be as simple as in 2-SAT.

However, there exist many works related to searching a polynomial-time algorithm for 3-SAT. The idea is to find criteria that can make the 3-SAT instance "Fixed-Parameter Trackable" (FPT).

I can recommend you the article On Fixed-Parameter Tractable Parameterizations of SAT by Stefan Szeider where there is a passage about seeing the SAT instance as a graph and searching a parameter in the graph to make the SAT problem trackable.

You can find more information about FPT here: https://en.wikipedia.org/wiki/Parameterized_complexity

I understand 2 SAT can be solved in Polynomial time finding out Strongly Connected Components. What about doing the same for 3SAT?

1 Answers1