Turing reducibility of 2 versions of the satisfiability problem

Question

I need help with this problem.

There are 2 versions of the satisfiability problem:

[1] decision version: determine whether an arbitrary formula f is satisfiable or not

[2] search version: if an arbitrary formula f is satisfiable, return an assignment of truth values to variables in the formula that makes f satisfiable. if f is unsatisfiable, return NIL.

Show that [2] is Turing reducible to [1].

I have to prove that the oracle algorithm of [1] entails that of [2] to say "[2] is Turing reducible to [1]".

I see that [2] is just the oracle algorithm of [1] since it discriminates the satisfiability of an arbitrary formula f.

Can this mean the oracle algorithm of [1] entails that of [2]? If can, what would be the reason?

Answer 1

Any algorithm that decides the satisfiability of a formula can also be used to find an assignment for a satisfiable formula:

While not all variables are assigned:

• Pick a variable and choose value 0.

• If formula is no longer satisfiable, replace value with 1.