patternModerate
Equisatisfiability in the reduction from 4-SAT to 3-SAT
Viewed 0 times
sattheequisatisfiabilityreductionfrom
Problem
So If I understood correctly, the conversion from 4-SAT statement to 3-SAT statement follows the following approach:
(a or b or c or d) -> (a or b or z) and (-z or c or d)
Where the z is a new literal. However, with 4 literals there exists 4^2 different permutations (a or b or c or d) and (-a or b or c or d) and (a or -b or...) and ...
If I convert each of the clauses with the approach above (add always new literal z_n and it's negation) like:
(a or b or z) and (c or d or -z) and (-a or b or z_2) and (c or d or -z_2) and ...
, then the resulting 3-SAT statement is indeed satisfiable. Even if the 4-SAT statement with the all permutations for 4 literals is not. They should be equisatisfiable?
(a or b or c or d) -> (a or b or z) and (-z or c or d)
Where the z is a new literal. However, with 4 literals there exists 4^2 different permutations (a or b or c or d) and (-a or b or c or d) and (a or -b or...) and ...
If I convert each of the clauses with the approach above (add always new literal z_n and it's negation) like:
(a or b or z) and (c or d or -z) and (-a or b or z_2) and (c or d or -z_2) and ...
, then the resulting 3-SAT statement is indeed satisfiable. Even if the 4-SAT statement with the all permutations for 4 literals is not. They should be equisatisfiable?
Solution
You're right in saying that they should be equisatisfiable. And they are.
I'm not sure why you think converting your unsatisfiable $4-\text{SAT}$ instance into a $3-\text{SAT}$ instance would make it satisfiable. Because it doesn't.
If a $4-\text{SAT}$ instance is unsatisfiable, then no matter how you choose to assign truth values to your variables, there will be some clause that is not satisfied. Without loss of generality, let that clause be $(a \vee b\vee c\vee d)$. Since this clause is not satisfied by your assignment, it follows that all of $a, b, c$ and $d$ are false.
Now converting this into a $3-\text{SAT}$ instance gives you these pair of clauses: $(a \vee b \vee z)(\neg z \vee c\vee d)$. Note that since $a, b, c$ and $d$ are all false, in order for both of these clauses to be satisfied, both $z$ and $\neg z$ need to be true, which is impossible.
In other words, the resulting $3-\text{SAT}$ instance is also unsatisfiable.
I'm not sure why you think converting your unsatisfiable $4-\text{SAT}$ instance into a $3-\text{SAT}$ instance would make it satisfiable. Because it doesn't.
If a $4-\text{SAT}$ instance is unsatisfiable, then no matter how you choose to assign truth values to your variables, there will be some clause that is not satisfied. Without loss of generality, let that clause be $(a \vee b\vee c\vee d)$. Since this clause is not satisfied by your assignment, it follows that all of $a, b, c$ and $d$ are false.
Now converting this into a $3-\text{SAT}$ instance gives you these pair of clauses: $(a \vee b \vee z)(\neg z \vee c\vee d)$. Note that since $a, b, c$ and $d$ are all false, in order for both of these clauses to be satisfied, both $z$ and $\neg z$ need to be true, which is impossible.
In other words, the resulting $3-\text{SAT}$ instance is also unsatisfiable.
Context
StackExchange Computer Science Q#88489, answer score: 10
Revisions (0)
No revisions yet.