This is actually exercise 3.7 from "Computational Complexity: A Modern Approach".

I need to prove that the NP-Completeness of 3-sat does not relativize, i.e. I need to show that that exists some oracle $A$ such that there exists $L\in \mathrm{NP}^A$ s.t. $L\not\leq_p\mathrm{3SAT}$, where the reduction can query the oracle for $A$. A lead of some kind would be most helpful (I know that using locality in the proof for Cook-Levin Theorem ruins the relativization, but it doesn't help me find an example).

Another question popped on the way (I hope it's ok): why is $\mathrm{EXP}$ not low on itself, i.e. why $\mathrm{EXP^{EXP}}\neq \mathrm{EXP}$? Cant I simply simulate the machine $M_L$ deciding some $\mathrm{EXP}$-Complete oracle $L$, for exponential number of steps and replace querying the oracle for input x with the output $M_L(x)$. Suppose $M\in \mathrm{EXP^L}$ runs in $2^{n^c}$ time, and $M_L$ runs in $2^{n^d}$, the machine replacing the oracle queries runs in at most $2^{n^c}\cdot2^{n^d}$ and is therefore in $\mathrm{EXP}$.


  • 1
    $\begingroup$ For your other question: $\:$ The oracle queries can be longer than $n$ bits. $\;\;\;\;$ $\endgroup$
    – user12859
    Commented Jan 31, 2015 at 10:38
  • 1
    $\begingroup$ Your second question is a perfectly reasonable question but it's completely unrelated to the first. Please copy-paste it into a new question and delete it from this one. $\endgroup$ Commented Feb 1, 2015 at 17:54
  • $\begingroup$ Additionally, note that "the NP-completeness of 3-sat does" relativize, since for all oracles $A$, $\hspace{.71 in}$ for all languages $\: L\in \operatorname{NP}^A \:$, $\:$ $\: L\leq_p \operatorname{3SAT}^A \:$, $\:$ so you'll need to focus on the "i.e." part. $\hspace{.94 in}$ $\endgroup$
    – user12859
    Commented Feb 2, 2015 at 3:40
  • $\begingroup$ The second question was answered by Ricky Demer. However, regarding your last commend, what you said is exactly what i need to disprove (and it's reasonable since the np completeness of 3-sat is based on that of SAT which is based on locality) $\endgroup$
    – Ariel
    Commented Feb 4, 2015 at 21:10