6
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Does something go wrong with showing that circuit-sat for circuits with oracle gates for a language A is complete for NP with oracle A, using the textbook proof? $\endgroup$ – Sasho Nikolov Nov 7 '14 at 23:21
  • 6
    $\begingroup$ 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 (just play a little bit with the oracle that separates P and NP). Obviously, if you allow oracle gates for an (arbitrary) oracle $A$, then you get that $\text{Circuit-}SAT^A$ is $NP^A$-complete as noted by Sasho. $\endgroup$ – Marzio De Biasi Nov 8 '14 at 0:56
  • $\begingroup$ Both answers sound good...care to post as answers so I can pick one to accept? $\endgroup$ – Philip White Nov 8 '14 at 15:35
  • $\begingroup$ I think Marzio should post. $\endgroup$ – Sasho Nikolov Nov 8 '14 at 17:59
  • $\begingroup$ @Philip White: The reason you received two apparently contradicting answers is that your question is ambiguous in the first place. You should clarify what you mean by the Cook-Levin theorem. I am afraid that it is not nice to keep the question ambiguous and ask both commenters to work more for you. $\endgroup$ – Tsuyoshi Ito Nov 8 '14 at 19:17
11
$\begingroup$

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|\}$

$\endgroup$
  • $\begingroup$ \ in $\mapsto$ \in $\;$ $\endgroup$ – user6973 Nov 9 '14 at 10:36
  • $\begingroup$ @MarzioDeBiasi, or anyone: I have a quick question on this answer. Do you know of a resource (textbook or preferably paper) that describes the proof that CircuitSAT^A is NP^A-complete? Thanks for your help. $\endgroup$ – Philip White Nov 29 '14 at 23:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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