1
$\begingroup$

Let $R$ be the set of all decidable languages. Consider $P^R$. That is, the set of all languages that can be decided via a polynomial time deterministic TM with an oracle to any language $L\in R$.

I'd like to show that $NP\subseteq P^R$. My intuition is to somehow define $NP=NP^{O(1)}$, and then to prove its a subset, yet when I tried doing so, I got tangled with the formalities of the proof itself .

Trying to prove by the definition of $NP$, that is to say that: a language $A\subseteq \Sigma^*$ is $A\in NP$ when a polynomial deterministic turing machine $M_A$ exists such that: $x\in A \leftrightarrow \exists y: \, M_A(x,y)=1$

It is left to show how construct a polynomial deterministic TM $N_A$ with an oracle to any $L\in R$, such that: $x\in A\leftrightarrow \exists L:\, N_A^{L}\left(x\right)=1$ When $N_A^L$ indicates a polynomial deterministic TM $N_A$ with an oracle to $L$.

While I can "fake" such a dummy $L$ with the language $A$ itself, I don't know how to disprove aby such language exists. That is, consider $x\notin A$. How can I show that $N_A^L$ will return false for any $L$?(The oracle is on $L$)

Hopefully I was able to explain my goal, my idea/method and where I got stuck on the proof. If any of those were unclear, please comment and I'd update my question accordingly.

Emphasizing my question: How can I construct a deterministic polynomial TM $N_A^L$ with an oracle to any $L\in R$ such that if $x\notin A$, it would not matter which $L\in R$ the TM $N_A^L$ will use for the oracle, the computation $N_A^L(x)$ would always result in a rejection of the input $x$?

Improve this question
$\endgroup$
1
  • $\begingroup$ Please don't use "edit". Instead, revise the question to what it should have been from the start. $\endgroup$
    – D.W. ♦
    Commented Jul 15 at 8:01

1 Answer 1

Reset to default
2
$\begingroup$

Let $L$ be SAT. Then it follows from the Cook-Levin theorem that $NP \subseteq P^L$. Now $L \in R$, so it follows that $NP \subseteq P^R$.

See also https://en.wikipedia.org/wiki/Oracle_machine#Complexity_classes_of_oracle_machines.

Improve this answer
$\endgroup$
7
  • $\begingroup$ But I do not choose a specific $L$. The TM $N_A^L$ should hold $x\in A \leftrightarrow N_A^L(x)=$true. So if $x\notin A$, how can I construct a TM $N_A^L(x)$ that will return false, no matter which $L\in R$ is selected as the oracle? (That's what I tried to emphasize in where I was stuck) $\endgroup$
    – Mařík Savenko
    Commented Jul 15 at 7:39
  • $\begingroup$ @MaříkSavenko, None of that is needed to prove that $NP \subseteq P^R$. I have given what I believe is a valid proof. I don't understand what approach you are trying to take, but it doesn't matter, because I have shown a simple way of proving $NP \subseteq P^R$, so there is no need to go into all that. Perhaps it would be worth reviewing the definition of oracle complexity classes. $\endgroup$
    – D.W. ♦
    Commented Jul 15 at 8:02
  • $\begingroup$ I'll give another shot of explaining what I find missing in this proof. If I construct a TM $N_A^L$ that constructs a CNF formula based on the TM $M_A$ of $A$ and would like to invoke an oracle for $SAT$, that would mean my TM $N_A^L$ would look of the sort: Given a language $A\in NP$, construct a CNF formula based on $M_A$ and then invoke the oracle for the language $L$ on the constructed formula. If $x\in A$ we can select $L=SAT$ and it will return true by Cook-Levin. Yet, if $x\notin A$? The oracle might be $\overline{SAT}\in R$, and it will return true. Meaning, true is returned both ways. $\endgroup$
    – Mařík Savenko
    Commented Jul 15 at 10:11
  • $\begingroup$ @MaříkSavenko, I think you have a misunderstanding about how oracle machines and the definition of oracle complexity classes. I suggest you first review the definition of what something like $P^{SAT}$ means and what $P^{NP}$ means. See the Wikipedia link I gave. One reasonable definition of $P^R$ is $P^R = \cup_{L' \in R} P^{L'}$. Since $SAT \in R$, it follows from this definition that $P^{SAT} \subseteq P^R$. Cook-Levin implies $NP \subseteq P^{SAT}$. Combining those two statements, we obtain $NP \subseteq P^R$. $\endgroup$
    – D.W. ♦
    Commented Jul 15 at 21:52
  • 1
    $\begingroup$ @MaříkSavenko, You don't have to do that. That's not part of the definition. There is no requirement to come up with an oracle machine that is correct for all instantiations of the oracle. I suggest studying the definitions. I think you have a misunderstanding of the definition. See the link in my answer. This site is intended for building a knowledge base that will be useful to others in the future. It's not especially designed for interactive tutoring or helping you debug misconceptions as you learn new subjects. $\endgroup$
    – D.W. ♦
    Commented Jul 16 at 1:21

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.