# Questions tagged [oracle-machines]

The tag has no usage guidance.

103 questions
Filter by
Sorted by
Tagged with
53 views

94 views

### Can the higher-order oracle Turing machines simulate the lower-order machines so that the current oracle does not contradict the simulated oracle?

Here is a quote from the Source 1: For example, if $M$ is a machine with an oracle for the halting problem, then obviously there isn't in general an equivalent machine that can simulate the ...
40 views

### Oblivious oracle TM's

In "The Complexity Theory Companion" Hemaspaandra and Ogihara define an oblivious oracle TM as an oracle TM where the queries are dependent on the input and not on the oracle. They then show how to ...
51 views

### Defining polynomial hierarchy with oracle machines and quantifiers

While trying to understand the concept of polynomial hierarchy, I noticed that there are several ways to define it. And the most confusing thing about the situation is to see the equivalence between ...
33 views

72 views

### On $UP$, $NP$, $\oplus P$ and $PP$?

We know $UP\subseteq NP\subseteq PP$. Is $UP^{\oplus P}\subseteq NP^{\oplus P}\subseteq PP^{\oplus P}$? I think the first $UP^{\oplus P}\subseteq NP^{\oplus P}$ is straightforward since whatever ...
51 views

### If the difference between two oracles is negligible, is the difference between a PPT algorithm with these two oracles also negligible?

We say a negligible function is a function $\epsilon(n):\mathbb{N}\rightarrow \mathbb{R}$ such that for every positive integer $c$ there exists an integer $N_c$ such that for all $n > N_c$, \...
44 views

### Is it possible to simulate oracle machines on 1-dimensional cellular automata?

My instinctual response is that it is possible, but I can't see how to simulate the oracle tape on a 1-d CA. If not, are they able to be simulated on n-dimensional CA? My thought is that the oracle ...
262 views

### Is the set of languages recognized by a Turing machine with an oracle countable?

I am currently taking a class in complexity theory and I am struggling with this question. We define a TM with Oracle per. Sipser 6.18 as: "An oracle for language $B$ is an external device that is ...
217 views

### A question on oracle turing machines

I am trying to solve a question from the exercise of this book, pg. 46,section 7.4. Let $M$ be a deterministic Turing machine that only queries oracle strings that are shorter than the input string. ...
295 views

58 views

63 views

### Showing if $A\in DSPACE(n^c) \text{ or } DTIME(n^c)$ then $EXP^A \neq EXP$ and $EXP^A= EXP$

If a language $A\in DSPACE(n^c)$, then $EXP^A\neq EXP$ If a language $A\in DTIME(n^c)$, then $EXP^A= EXP$ What I tried: Since it's impossible to show that $EXP \subseteq EXP^A$ because: We ...
132 views

### What does it mean for a problem to be solved in polynomial time “relative to” an oracle?

I came across the following theorem in page 12 of the following pdf : There exists an oracle relative to which there is a problem solvable in polynomial time (with bounded error probability) on a ...
92 views

### Are all proof techniques which only look at black box behaviour of a TM relativizing?

I am currently working on a seminar on $\mathbf{P \stackrel{?}{=} NP}$ and one of the points I want to adress is the Relativization barrier. However, it is hard to find a concrete definition of a "...
303 views

### What is an approximation oracle?

I have seen the term "approximation oracle" in computer science papers, sometimes parameterized with the letters $\alpha$ and $\beta$. What is an approximation oracle? How are such oracles used? I am ...
65 views

### Question about $\mathsf{Almost–PSPACE}$

A language is in $\mathsf{Almost\text{-}PSPACE}$ if there is a (deterministic) $\mathsf{PSPACE}$ Turing machine with an oracle $A$ that accepts the language with probability $1$ when the ...
67 views

### On oracle access containment?

If $X,Y$ are complexity classes in the polynomial hierarchy with $X\subseteq Y$. With abuse of notation assume $X,Y$ also as the TMs that accept languages in classes $X,Y$ respectively. Then is it ...
754 views

### Why can't we simulate an NP oracle with an NP machine?

In this question : Does $NP^{NP}=NP$? , it says that one of the reason is that we don't know how to detect 'no' answers from the oracle. Why is that true though? There is an NTM for any language L in ...
I am struggling to understand how the known oracle, and conditional derandomization results connecting $BPP$ and $P$, relate to each other. My understanding is that if there is a suitably strong ...