Reducibility of 2 boolean satisfiability problems

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$?

Answer 1

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.