So a few days ago my lecturer told us that for every nondeterministic polynomial time oracle machine $M$, there is a nondeterministic polynomial time oracle machine $N$ that gives us $L(N^{3-SAT}) = L(M^{3-SAT})$ and $N$ makes a single query to its oracle. He didn't give us a clear explanation for why this is true.

My explanation for that would be that if machine $M$ has $k$ queries for the $3-SAT$ oracle named $q1,q2...qk$ then for every query $qi$ out these queries we either ask if $qi \in 3-SAT$ or $qi \notin 3-SAT$. The single query for machine $N$ would be defined like this $Q' =$ ($Q1$ AND $Q2$ AND $...$ $Qk$) and we define:

$Qi = qi$ if we are asking $qi \in 3-SAT$ in machine M.

$Qi = NOT(qi)$ if we are asking $qi \notin 3-SAT$ in machine M.

We give the query $Q'$ to the $3-SAT$ oracle of machine $N$ and if it is true then we get $L(N^{3-SAT}) = L(M^{3-SAT})$.

Are there any problems in my explanation ? Is there a better explanation ?


1 Answer 1


Your idea is in a good direction. To complete this proof, you will need to note a few things, and explain why they are not problems (or how to fix them):

  1. The new machine will only do one oracle call at the end. That means, that at any time that our original TM did an oracle call, it wont get an answer!

  2. We need to "save up" and "remember" which oracle calls we want to do, until we finish the execution. Why won't this take us too much time or space?

And here is how to fix them:

  1. Ask from the prover to give you a boolean number $b_i\in\{0,1\}$ representing the "output" of the $i$'th query. In this sense, the prover replaces the oracle, and you ask it instead of the oracle. Then, at the end we will need to verify this against the original oracle (think how to do this!)

  2. The machine will execute at most a polynomial number of steps. Lets denote that by $P_1(x)$. Now, this means that the number of oracle calls (and the size of each oracle call) won't exceed $P_1(x)$. But, to manage and store the oracle calls we might need $P_2(y)$ time for $y$ being the number of oracle calls. Therefore, we will need at most $P_2(P_1(n))$ time overall to manage the oracles, when $n$ is the size of the input. This is only a polynomial factor, and since we are dealing with $NP$, then this is OK!

Additional explanation on how to verify that the $b_i$'s are correct from the first part:

Define $B_{true}=\{i\mid b_i=1\}$ and similarly $B_{false}=\{j\mid b_j=0\}$. Now, define $Q'_{true}=\bigwedge\limits_{i\in B_{true}}{Q_i}$ while changing the variable names in the $Q_i$'s to be disjoint (this is important!).

Now, we want to define $Q'_{false}$ in a similar way that will capture all $B_{false}$ indices. To do that, we need to take a small walk to the realm of the general SAT problem. For starters, we will assume without loss of generality that the indices of $B_{false}$ are $1,\dots ,k$. Now, let us define auxiliary variables $a_i$ for all $1\le i\le k$. We will use those auxiliary variables to "select" which $Q_i$'s we want to show that has \ doesn't have a satisfying assignment. To do that, let us define $Q'_i:=\lnot a_i \lor Q_i$, that will be built by adding $\lor \lnot a_i$ to each clause in $Q_i$. Notice that if some $a_i$ is $true$, then we need a satisfying assignment of $Q_i$ to satisfy $Q'_i$. But if $a_i$ is $false$, then $Q'_i$ is immediately satisfied. We will need to make sure at least one of the $a_i$'s is $true$, in order to ensure that at least one of the $Q_i$'s will have to be satisfiable. To do that, consider the clause $(\lnot a_1 \lor \lnot a_2 \lor \dots \lor \lnot a_k)$. Now, we are ready to finally define $Q'_{false}$! We will define it as: $Q'_{false}:=(\lnot a_1 \lor \lnot a_2 \lor \dots \lor \lnot a_k)\land \left(\bigwedge\limits_{i=1}^k Q'_i\right)$.

Convert this $Q'_{false}$ to $3-CNF$ form using the $SAT\le_p 3-SAT$ reduction, and then ask this as the only single query you need to do. You are guaranteed to get back $0$ if all $Q_j$'s for $j\in B_{false}$ were not satisfiable, since if one of them would have been satisfiable, then we could satisfy $Q'_{false}$ by choosing the auxiliary variable to "select" that satisfiable $Q_j$, and satisfy $Q_j$. Then, all other $Q_{j'}$ were not "selected" and hence automatically we have that $Q'_{j'}$ are satisfied, leaving us with that $Q'_{false}$ is itself satisfied.

  • $\begingroup$ Thanks for the notes. Regarding the first note, because the single query for machine $N$ is defined as $Q' =$ ($Q1$ AND $Q2$ AND $...$ $Qk$) then I can define $B = 1$ if $Q' \in 3-SAT$ and $B = 0$ if $Q' \notin 3-SAT$. Now regarding the prover of machine $M$ I have $b1,b2...bk$ the results of my queries. In order to verify these results against the original oracle we check if $B =$ ($b1$ AND $b2$ AND $...$ $bk$). Is this valid ? $\endgroup$
    – CSDude101
    Jul 5, 2021 at 17:53
  • $\begingroup$ Regarding the second note, will be there any problem if I have exponential number of queries for machine $M$ ? $\endgroup$
    – CSDude101
    Jul 5, 2021 at 17:56
  • $\begingroup$ @shadihelf for the first note, no. that is not allowed. Since then if we have one $b$ that is $0$, then $B$ will have to be $0$ as well. The solution for that is a bit more tricky (it involves another trick using the prover), so I will add an additional explanation on it. For the second note, yes, there will be a problem. For one, your machine is polynomial so it cant store an exponential number of queries. But since the machine is polynomial it never would have needed an exponential number of queries anyways. $\endgroup$
    – nir shahar
    Jul 5, 2021 at 18:11
  • $\begingroup$ Upvoted for the great explanation of the first note! I have one last question regarding your approach. Towards the end of your explanation you mention that after converting $Q'false$ to $3-CNF$ then it is enough to ask machine $N$ about the query $Q'false$ in it's $3-CNF$ form. However what about the query $Q'true$ ? Shouldn't you convert the query ($Q'true$ AND $Q'false$) to $3-CNF$ then ask the $3-SAT$ oracle of machine $N$ about this query in it's $3-CNF$ form ? $\endgroup$
    – CSDude101
    Jul 6, 2021 at 11:51
  • $\begingroup$ @shadihelf thanks! About that, you can actually create $Q'_{true}\land Q'_{false}$ and give that to the oracle if you want. Its equivalent to asking $Q'_{false}$ in the oracle and verifying $Q_{true}$ using the regular prover. $\endgroup$
    – nir shahar
    Jul 6, 2021 at 11:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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