Return to Question

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.

Edit 1: Mixed non-deterministic and deterministic, fixed and in bold.

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$?

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$?

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.

Edit 1: Mixed non-deterministic and deterministic, fixed and in bold.

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.

Edit 1: Mixed non-deterministic and deterministic, fixed and in bold.

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$?

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

I'd like to show that $NP\subseteq NP^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 non-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 non-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.

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.

Edit 1: Mixed non-deterministic and deterministic, fixed and in bold.