TITLE: Does the Cook-Levin theorem relativize?
QUESTION [6 upvotes]: My only motivation for asking this question is long-standing curiosity, but I am interested in seeing a proof (or disproof) that the Cook-Levin theorem relativizes.  If you have a proof that the theorem does indeed relativize, please supply an explanation of how relativization impacts the proposition, i.e., what does the relativized version of the statement look like when an oracle A is added?  Also, please explain what happens to the proposition when a TQBF oracle is added to the computation model.

REPLY [12 votes]: From the comment above: there are two interpretations to your question:
1) The Cook-Levin theorem does not relativize in this sense: there exists a language $L$ and an oracle $A$ such that $L \in NP^A$ but $L$ is not polynomial-time many-one reducible to $3SAT$ even if the polynomial time Turing machine that performs the reduction is allowed to access the same oracle $A$ (i.e. $L \nleq_m^A 3SAT$). The proof is a standard exercise (see for example Arora and Barak, Computational Complexity); hint: play a little bit with the oracle that separates P from NP, the only difference here is that you must "fool" polynomial-time oracle Turing machines that output 3SAT formulas instead of deciders that output yes/no (let me know if you need the full proof);
2) The Cook-Levin theorem does relativize in this sense: you  can extend the circuit model with oracle gates, i.e. $k$-inputs gates in which the inputs are ordered and the output bit is the result of the associated oracle on the query formed by the ordered input bits (there is also a variant in which every bit of the query is represented by two input bits, in order to allow queries shorter than $k$). With this extended oracle circuit model you can build in polynomial time a polynomial-size oracle circuit $C^A$ that "simulates" - in a similar way of the Cook-Levin theorem - the computation of an oracle polynomial time machine $M^A$ and on input $x$ evaluates to 1 if and only if $M^A(x)=1$. So, if 
$\text{Circuit-}SAT^A = \{ C \mid C $ is a boolean circuit equipped with oracle gates for $A$ and for which there exists $x$ such that $C(x)=1 \}$ you say that:
for every oracle $A$, $\text{Circuit-}SAT^A$ is $NP^A$-complete.
3) Finally with a TQBF oracle we have $P^{TQBF} = NP^{TQBF}$, so if we add a TQBF oracle to the polynomial time Turing machine that performs the reduction (interpretation 1) we give to it the power to solve the original problem directly, so we have: $NP^{TQBF} \leq_m^{TQBF} \{1\}$ i.e. every trivial set is $NP^{TQBF}$-complete under polynomial time many-one TQBF-oracle reductions (except $\emptyset$ and $\Sigma^*$ :-), so Cook-Levin theorem does relativize for the TQBF oracle (solve the source instance and output $(x_1 \lor x_2 \lor x_3)$ if it belongs to the language, output an unsatisfiable 3SAT formula otherwise).
Addendum: related to your question, it is interesting how the (old but great) Computational Complexity by C. Papadimitriou explicitly faces the problem of the relativization of another well known thereom, the Ladner's theorem, in this way (probably the oracle gates were introduced later): 
[From Chapter 14]: ... "If $P^A \neq NP^A$, then there is a language in $NP^A - P^A$
which is not $NP^A$-complete". But when we say "$NP^A$-complete", do
we also allow the use of oracle in our reductions?
With a little reflection we may decide that the
right way to state the result is in terms of ordinary reductions...
..... There seems to be no reasonable definition of $SAT^A$.
To get around this difficulty, we must replace the usage of SAT
with an $NP^A$-complete problem. Such problem exist; for example:
$C^A = \{ (M^A,x) \mid $ nondeterministic  oracle machine $M^A$ accepts $x$ in time $|x|\}$
{"set_name": "stack_exchange", "score": 6, "question_id": 27377}