The following is an exercise which I am stuck at ( source: Sanjeev Arora and Boaz Barak; its not homework ) :

Show that there is an oracle $A$ and a language $L \in NP^A$ such that $L$ is not polynomial-time reducible to 3SAT even when the machine computing the reduction is allowed access to $A$.

What I tried was, take $A$ to be the oracle to halting problem and let $L=\{1^n | \;\exists \; \langle M,w \rangle \; \text{s.t.} \; |\langle M,w \rangle|=n \; \text{ and Turing machine M halts on w} \} $.

With this assignment I ensure $L \in NP^{A}$ and $L$ is not polynomial reducible to 3SAT if oracle is not provided to the machine carrying out reduction. Although to map an instance $1^n$ I would have to search through $2^n$ strings even if oracle is provided to the reduction machine. But this does not seem like a proof for absence of polynomial reduction in this case.

Is there a way to prove it using the same example ? Is there a simpler example ?


1 Answer 1


Please refer Does Cook Levin Theorem relativize?.

Also refer to Arora, Implagiazo and Vazirani's paper: Relativizing versus Nonrelativizing Techniques: The Role of local checkability.

In the paper by Baker, Gill and Solovay (BGS) on Relativizations of the P =? N P question (SIAM Journal on Computing, 4(4):431–442, December 1975) they give a language $B$ and $U_B$ such that $U_B \in NP^B$ and $U_B \not\in P^B$, thus proving that there are oracles $B$ for which $P^B \neq NP^B$.

We shall modify the $U_B$ and $B$ to $U_{B'}$ and $B'$ such that we get a new language that cannot be reduced to 3SAT even if there is availability of $B'$ as an oracle.

First assume that we can pad every $3SAT$ boolean instance $\phi$ to $\phi'$ with some additional dummy 3CNF expressions such that $|\phi'|$ is odd and they are equivalent, i.e., $\phi$ is satisfiable iff $\phi'$ is satisfiable. We can do it in $n+O(1)$ time and with $O(1)$ padding, but even if it takes polynomial time and extra polynomial padding it does not matter.

Now we need to combine the $B$ and $3SAT$ to $B'$ somehow so that BGS theorem still holds but additionally $3SAT \in P^{B'}$. So we do something like the following.

$U_{B'} = \{1^n \ \ |\ \ \exists x \in B, $ such that $|x| = 1^{2n}\}$ and

$B' = B'_{constructed} \ \cup \{\phi \ \ |\ \ \phi \in 3SAT $ and $ |\phi| $ is odd $\}$.

Now we shall construct $B'_{constructed}$ according to the theorem such that if the deterministic machine $M_i^{B'}$ for input $1^n$ ($n$ is determined as in theorem) asks the oracle $B'$ a query of odd length we check if it is in $3SAT$ and answer correctly but if it asks a query of even length we proceed according to the construction, that is, answering correctly if it is already in the table, otherwise answer no every time. Then since we are running for $1^n$ we flip the answers at $2n$ length so that $M_i^{B'}$ does not decide $U_{B'}$.

We can prove similarly as in the BGS theorem that for this $B'$ and $U_{B'}$ too, we have $U_{B'} \in NP^{B'}$ and $U_{B'} \not\in P^{B'}$.

$U_{B'} \in NP^{B'}$ is easy to prove. We construct a non-deterministic Turing Machine which for input $1^n$ creates non-deterministic branches that runs for $2n$ steps to generate a different $2n$-length string and then asks oracle $B'$ if the $2n$-length string is in $B'$, and if the answer is yes it accepts $1^n$ else it rejects $1^n$. This construction shows that $U_{B'} \in NP^{B'}$.

$U_{B'} \not\in P^{B'}$ can be proved with the help of diagonalization argument. Basically it is different from every $L(M_i^{B'})$ for every oracle Turing Machine that have $B'$ as an oracle. This is because of how we construct $B'_{constructed}$.

Now we shall prove by contradiction that there does not exist a reduction from $U_{B'}$ to $3SAT$ even with the availability of oracle $B'$.

Assume there is a reduction using oracle $B'$, i.e., $U_{B'} \leq^{B'}_P 3SAT$.

That means we can reduce a string of the form $1^n$ to a 3SAT instance $\phi$ using a polynomial-time deterministic machine which uses $B'$ as oracle.

We can now describe a deterministic TM $M^{B'}$ which will decide strings $U_{B'}$ in polynomial time using $B'$ as an oracle. First this machine reduces the input $1^n$ to a 3SAT-instance $\phi$ using $B'$ as an oracle. This can be done because we have the reduction above. Then if $\phi$ is not odd length $M^{B'}$ will pad it to make $\phi'$ which is odd length. Next, it will give this $\phi'$ to oracle $B'$ and get the answer yes/no. It will accept if the answer is yes and reject if the answer is no.

This machine is deterministically polynomial and uses oracle $B'$.

Thus we have proved that $U_{B'} \in P^{B'}$, a contradiction.

Therefore $U_{B'} \not\leq^{B'}_P 3SAT$.

  • $\begingroup$ How is $L \in P^{B}$ possible ? I would decide membership of $L$ in polynomial time and map it to a small SAT formulae depending on the membership of string. Am I missing something ? $\endgroup$ Commented Feb 21, 2016 at 11:55
  • $\begingroup$ The first link does not give the proof. Could you give any hints why that language $U_{B}$ mentioned in Sanjeev Arora and Barak is not polynomial time reducible to 3SAT. Also the second link does not work. $\endgroup$ Commented Feb 21, 2016 at 15:43
  • $\begingroup$ How does $U_B^{'} \in NP$ ? Doesn't each branch of non determinisitic Turing machine run for 2^n ? $\endgroup$ Commented Feb 22, 2016 at 9:51
  • 1
    $\begingroup$ Notice I have redefined $U_{B'}$. Also $U_{B'} \in NP^{B'}$. It may not (does not!!) belong to $NP$. $\endgroup$ Commented Feb 22, 2016 at 9:55
  • 1
    $\begingroup$ Each branch runs for $2n$ steps to generate a different $2n$-length string and then asks oracle if it is in $B'$, and if the answer is yes it accepts else it rejects $1^n$. $\endgroup$ Commented Feb 22, 2016 at 9:58

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.