Timeline for Non-deterministic TM with an oracle to $R$
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 16 at 1:21 | comment | added | D.W.♦ | @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. | |
| Jul 15 at 22:10 | comment | added | Mařík Savenko | The problem is when we refer to the entire set of $R$, and not just for a single language (say, $SAT$). How can we describe a DPTM $N_A$ that will reject an input $x$ s.t. $x\notin A$, for any selection of $L\in R$? Like I said prior, using Cook-Levin to construct a CNF-formula that describes the computation of the TM for $A$ is simply not enough, because the oracle to be invoked might be $\overline{SAT}\in R$. (Yes, I passed over the definitions in the page, I usually use the oracle as a Yes/No version). | |
| Jul 15 at 22:08 | comment | added | Mařík Savenko | Perhaps the notion $P^R$ is misleading here. When considering $P^{SAT}$, you have a DPTM (deterministic, polynomial) with an oracle to $SAT$. Yet, when you consider a set of languages, the oracle may be to any such language of the given set. In my example, $P^R$ may invoke any language (or its complement) from $R$. When considering a DPTM with an oracle to $R$, I do not consider a specific language from $R$. I refer to a DPTM that can invoke an oracle for any $L\in R$. Meaning, the DPTM I am attempting to find, say $N_A$, should be able to invoke an oracle to ANY language $L\in R$. | |
| Jul 15 at 21:52 | comment | added | D.W.♦ | @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$. | |
| Jul 15 at 10:11 | comment | added | Mařík Savenko | 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. | |
| Jul 15 at 8:02 | comment | added | D.W.♦ | @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. | |
| Jul 15 at 7:39 | comment | added | Mařík Savenko | 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) | |
| Jul 15 at 7:20 | history | answered | D.W.♦ | CC BY-SA 4.0 |