i just want to know why the techniques we use to solve the 2-SAT problems cannot be used to solve the 3-SAT problem. So the techniques that i know that help solve 2-sat are the naive on where you just take one variable in the formula and give it a truth value and go on from there by deleting clauses where the variable is in it and so on. Why won't that work for 3-SAT so when i chose a variable and set it to true i do the same things that i would do for 2-SAT, shouldnt that also work? The second technique that i know that helps solve 2-SAT is where you create an implication graph from the formula with 2 implications per clause with the form being a$\Rightarrow$b, where a and b are literals. if i convert that to 3-SAT i could generate 3 implications per clause a$\Rightarrow$b$\lor$c where a,b and c are literals. why won't that algorithm work for 3-SAT the same way it works for 2-SAT?
2
-
2$\begingroup$ Have you tried your proposed algorithms on 3SAT? $\endgroup$– Yuval FilmusCommented Jun 25, 2022 at 17:05
-
3$\begingroup$ Can you explain why your algorithms work for 2SAT? Do the same proofs carry on to 3SAT? $\endgroup$– Yuval FilmusCommented Jun 25, 2022 at 17:05
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The issue might be that 2SAT can be solved in polynomial time while 3SAT is NP-complete and can't. When the computational complexity becomes much higher, the proofs of your 2SAT method might not translate well to 3SAT or it works but you just don't have time to wait around for the solution.
It's hard to say unless you tell us what you mean by "work".
As I understand, going from 2 to 3 SAT you're changing the information structure of the problem a lot. So a lot can go wrong.
