14

Just take a problem whose Turing degree is above $0'$, which is the degree of The Halting Oracle. In terms of the arithmetical hierarchy you want problems which are above $\Sigma^0_1$. Examples of such problems (where $\phi_n$ is the $n$-th partial computable function and $W_n = \{k \in \mathbb{N} \mid \text{$\phi_n(k)$ is defined}\}$ is the $n$-th ...


13

Sure, you just have to be careful thinking about what it means to have an oracle. The problem comes from an annoying abuse of notation we use in CS: In the statement $P=NP$, $P$ refers to a set of languages. But in the statement $P^A = NP^A$, $P$ refers to a class of Turing Machines (determinstic polytime TMs). You should think of these two $P$s as of ...


12

Oracles are a very general formalization of the idea, "If I could solve $X$ efficiently, I could use that to solve $Y$ efficiently." I accept that it sounds a bit silly to go as far as "If I could solve problem $X$ in constant time, I could use that to solve $Y$ efficiently" but, actually, that doesn't make any real difference at the ...


12

$\mathrm{BQP}^{\mathrm{BQP}} = \mathrm{BQP}$ has been proved in Strengths and Weaknesses of Quantum Computing Bennett et al. (arXiv). According to the complexity zoo, $\mathrm{ZBQP}^{\mathrm{ZBQP}} = \mathrm{ZBQP}$.


10

Here are some answers to some of the questions, but certainly not all of them: Apparently, according to Wikipedia, we have $P^P=P$, $BPP^{BPP}=BPP$, $PSPACE^{PSPACE}=PSPACE$, $L^L=L$, and $\oplus P^{\oplus P} = \oplus P$. See also What is complexity class $\oplus P^{\oplus P}$, which observes that $\oplus P^{\oplus P} = \oplus P$. Also, if $C^C=C$, then $...


10

No, an oracle is a black box that solves a problem in a single step. The problem that it solves can be any problem, it doesn't need to be the halting problem. What Scott is saying is that there is some black box that a BQP machine with it can do more than what a BPP machine can do with it. However, it doesn't mean that without that black box BQP is more ...


10

There are several applications to oracles. First, there is usage in proving lower bounds (i.e. Turing reductions): if you know that a problem $L$ cannot be solved within some complexity (or computability) class $C$, and you show that an oracle to $L'$ allows you to solve $L$ within $C$, then you can conclude that $L'$ is also not in $C$. Second, there is ...


8

Let me try to answer your multifaceted question using an analogy from number theory (or rather, Peano arithmetic). The platonist point of view holds that every question about natural numbers has a YES/NO answer. This is known as "true arithmetic". However, as Gödel showed, some propositions concerning natural numbers can be neither proved nor disproved. The ...


8

There's a number of ways to look at this. One is that in proofs, implication is kind of like a function, that takes as input a proof of something, and outputs a proof of something else. We can write functions that operate on values that we don't have. For example, let's consider the halting number $h$, which is not computable. I can write the function $...


8

Why are oracles used in the context you mentioned (where we have an oracle for the halting problem)? Because that allows us to answer questions that are fascinating, questions like "Are there problems that are even harder than the halting problem?". I'm not saying these questions are necessarily useful or important in practice -- but they are fascinating, ...


8

Please refer Does Cook Levin Theorem relativize?. Also refer to Arora, Implagiazo and Vazirani's paper: Relativizing versus Nonrelativizing Techniques: The Role of local checkability. In the paper by Baker, Gill and Solovay (BGS) on Relativizations of the P =? N P question (SIAM Journal on Computing, 4(4):431–442, December 1975) they give a language $B$ ...


8

No, $\mathsf{EXP^{EXP}=2EXP}$, a set of languages decidable in $O\left(2^{2^{\mathrm{poly}(n)}}\right)$ time. This is just because you can give exponentially long input to an oracle which can solve it. So, the total power is $\exp(\exp(n))\ne \exp(n)$. To see why $\mathsf P$ is self-low just take a machine that can run quadratic time and give to it the ...


7

For an oracle $A\in {\sf P}$ you have ${\sf P}^A={\sf P}$ (since you can encode all requests to the oracle as a submodule of the TM). By the same argument you als have that ${\sf NP}^A={\sf NP}$. Thus in this case ${\sf NP}^A\neq{\sf P}^A$ would imply ${\sf NP}\neq{\sf P}$. You basically said this already in your question. Note that we cannot query "...


7

It is not true that for $A$ being $\sf EXP$-complete ${\sf DTIME}^A(n^k) = {\sf EXP}$, but you are right with ${\sf P}^A={\sf EXP}$. Here is the reason for this. In order to make use of the oracle you have to transform your problem via a reduction. This reduction is a polynomial reduction. The running time of this particular reduction might need $\omega(n^k)...


7

The proof of the time hierarchy theorem relativizes. This means that all the steps remain true if all Turing machines are given access to the same oracle $O$ (for arbitrary $O$). This implies that the theorem itself remains true if all Turing machines are given access to the oracle $O$. So yes, it is possible to prove that no oracles exist with respect to ...


6

There are many mathematical objects that "do not exist" (afaik, and whatever that means), and which have been the support of mathematical reasonning for centuries (maybe not many centuries). The first example that comes to mind is the real numbers, and more generally non denumerable sets. All you need is that the non-existing object have properties that are ...


6

A complexity class $ C $ is called self-low precisely when $ C^C = C $. In general, "lowness" was studied a lot in the 80s and 90s -- google will uncover much for you.


6

Krentel gave two problems complete for $\Delta_2^P$ (see Theorem 3.4): Input: Boolean formula $\phi(x_1,\dots,x_n)$. Question: Is $x_n = 1$ in the lexicographically largest satisfying assignment of $\phi$? Input: Weighted graph $G$, integer $k$. Question: Is the length of the shortest TSP tour in $G$ divisible by $k$? Krentel also states that ...


6

The proof that a Turing machine with an oracle for $X$ can't solve the halting problem for Turing machines with an oracle for $X$ is identical to the proof that an ordinary Turing machine can't solve the halting problem for ordinary Turing machines.


5

It's open whether $\mathsf{BPP} \subseteq \mathsf{P}^{\mathsf{NP}}$. The best we can currently say about $\mathsf{BPP}$ is that it is contained in S2P, a class contained in $\Sigma_2 \cap \Pi_2$ and $\mathsf{ZPP}^{\mathsf{NP}}$. See references given at Wikipedia. If $\mathsf{BPP} \subseteq \mathsf{P}^{\mathsf{NP}}$, then this fact does not relativize (...


5

Some optimization algorithms are formulated as algorithms for an oracle Turing machine. This is common, among else, in submodular optimization. An algorithm for minimizing or maximizing a submodular function given some constraints typically has oracle access to the submodular function (and sometimes to the list of constraints). This has the advantage of ...


5

Well, nowhere does the answer claim the reduction "implies that the original problem is in NP". So, that explains your confusion. You read something into the answer that isn't actually there. Also, the answer says "Cook reduction". This was a heads-up about the fact that it's not the Karp-style reduction you might be used to. You might like to learn ...


5

The answer in its current form shows only that it belongs to $\Delta_2^P$, or $P^{NP}$. This is a (not necessarily strict) subset of $\Sigma_2^P$, or $NP^{NP}$, which is what the asker had mentioned. The answerer said that they don't know whether it's $\Delta_2$-complete, but doubt it; and it similarly seems unlikely that this in $NP$. (The next answer ...


5

An approximation oracle for an optimization problem $X$ is an oracle which accepts an instance of $X$ and returns an approximate optimum. The parameters $\alpha,\beta$ quantify the quality of the approximation. Approximation oracles are a formal way of stating results of the following form: Given a polynomial time $C$-approximation algorithm for $X$, ...


4

Take $A=NP$, as you requested. $P^{NP}$ is not necessarily equal to $NP$. Let me give an example why not. Consider TAUTOLOGY (given a boolean formula $\varphi$, is it true for all possible assignments to the variables?). TAUTOLOGY is known to be co-NP-complete. Therefore, TAUTOLOGY most likely is not in NP, since if TAUTOLOGY were in NP, it would follow ...


4

An oracle is just a theoretical device which will provide the answer to a given class of decision problems in a single step. We say that a decision problem is in $BPP$ relative to the oracle if a turing machine (or whatever model of computation you are using) with access to the oracle can answer the decision problem in a polynomial amount of time with ...


4

Every problem $P$ can be solved with an oracle machine with oracle access to $P$. In order to get a more meaningful answer, we consider the concept of Turing semi-degree, which is the set of all problems computable with an oracle to $P$, for some problem $P$. The same diagonalization argument used to prove that the halting problem isn't decidable shows that ...


4

Using the definition of Papadimitrou for polynomial hierarchy, or for that matter from wiki, the proof is really simple. $\Delta^P_{k+1} = P^{\Pi_k^P} \subseteq CoNP^{\Pi_k^P} = CoNP^{\Sigma_k^P} = \Pi^P_{k+1}$. Similarly $\Delta^P_{k+1} \subseteq \Sigma^P_{k+1}$. But if the definition of polynomial hierarchy is done by alternating quantifiers than also we ...


Only top voted, non community-wiki answers of a minimum length are eligible