Reducibility of 2 boolean satisfiability problems
-
29-09-2020 - |
Question
I beg some help with this problem.
There are 2 boolean satisfiability problems.
Problem $A$: Determining whether an arbitrary formula of size $n$ is $satisfiable$.
Problem $B$: Determining whether an arbitrary formula of size $n-1$ is $satisfiable$ in which $n$ is a positive integer $\ge 2$Prove that $A$ can be solvable if $B$ is solvable.
I guess the solution would be showing that $A$ is Turing-reducible to $B$. It means I have to show the oracle algorithm of $B$ derives the oracle algorithm of $A$.
As you see, the arbitrary formula of $B$ is $n-1$, but that of $A$ is $n$. How can I suppose to entail the oracle algorithm about $A$ from the oracle of $B$, which is determining the formula of 1-less size than that of $B$?
Solution
Problem A is reducible to Problem B in following manner:
- Pick a variable in problem A and set it to 0
- Now we have a formula of size n-1, if satisfiable with B then return satisfiable
- Else, pick problem A again and set the variable to 1
- Now we have a formula of size n-1 again, if satisfiable with B then return satisfiable else return unsatisfiable
In other words: Split problem A into two problems B using any variable. If B says unsatisfiable for both 0 and 1 then it is unsatisfiable. If it says satisfiable for at least one of the two, then it is satisfiable.