1
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.