Turing machine $\textbf{M}$, which ran in polynomial time, with an oracle

Question

My question is I required to prove that there exists a deterministic Turing machine $\textbf{M}$, which ran in polynomial time, with an oracle approach to the $\texttt{SAT}$ language, such that: Given an input $\phi$- the $\texttt{3CNF}$ formula over the variables $u_1, u_2,\dots u_n$- $\textbf{M}$ returns a satisfying assignment for $\phi$, if one exists and a special sign $\perp$ otherwise. All this - while $\textbf{M}$ performs at most $n$ queries to Oracle.

My attempt: We can construct a deterministic Turing machine $\textbf{M}$ that runs in polynomial time and makes at most $n$ queries to an oracle for the SAT language. $\textbf{M}$ queries the oracle on modified versions of the 3CNF formula $\phi$ , where each query assigns values to a subset of the variables $u_1, u_2, \dots, u_n$ , and checks whether a satisfying assignment still exists. By querying the oracle iteratively, each time fixing one variable based on the oracle’s response, $\textbf{M}$ can either construct a satisfying assignment or conclude that none exists after at most $n$ queries. Thus, $\textbf{M}$ either returns a sufficient assignment for $\phi$ or outputs the special symbol $\perp$ (if no satisfying assignment exists).

But my approach seems to be confusing because I can't explicitly explain how the machine ensures polynomial time complexity while making $n$ oracle queries.

Is there any different to prove the theorem? Any help is appreciated.

Answer 1

Denote $\phi_{\top\leftarrow u_i}$ the formula $\phi$ where each occurrence of $u_i$ is substituted by $\top$ (and similarly $\phi_{\bot\leftarrow u_i}$).

Denote a call to the oracle with formula $\phi$ as oracle$(\phi)$, and assume it returns either $\top$ (if the formula is satisfiable) or $\bot$ (if not).

The algorithm is the following:

• if oracle$(\phi)=\bot$, return $\bot$
• for $i = 1$ to $n$:
  • if oracle$(\phi_{\top\leftarrow u_i})=\top$:
    • $\mu(u_i) = 1$
    • $\phi \leftarrow \phi_{\top\leftarrow u_i}$
  • else:
    • $\mu(u_i) = 0$
    • $\phi \leftarrow \phi_{\bot\leftarrow u_i}$
• return $\mu$

The returned assignment is indeed a satisfying assignment of the initial $\phi$. There are $n$ calls to the oracle, and the computation of $\phi_{\top\leftarrow u_i}$ is done in polynomial time; it can be transformed as a 3CNF, by deleting each clause containing $\top$ (or $\neg \bot$), and each literal $\bot$ (or $\neg \top$).