# Tag Info

Accepted

### Detecting if three Turing Machines halt given a magic oracle that is only used twice

One way to built $T_A$ works is roughly as follows: ...
• 3,105
Accepted

### How can I show that the Cook-Levin theorem does not relativize?

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 ...
• 4,817
Accepted

### Oracle Turing Machine EXP^EXP

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 ...
• 1,632

### Detecting if three Turing Machines halt given a magic oracle that is only used twice

As Arno shows in the other answer, you can easily write a program that halts if and only if at least $k$ out of $n$ given Turing machines halt, by running the $n$ machines in parallel until $k$ of ...
• 181

### Oracle machine solving halting problem for other oracle machines

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 ...
• 81.7k

### What is an approximation oracle?

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 ...
• 277k
Accepted

• 277k

### Do relativized relations between complexity classes tell us anything about the nonrelativized relation?

I am by no means an expert, but 2 things come to mind: Because if we know things like $A^L \neq B^L$, for some $L$, then a proof of $A = B$ need to be non-relativizing. This puts constrains on the ...
Accepted

• 160k

### What is the relation of complexity class $L^L$ to other complexity classes?

$L$ is self-low, i.e. $L^L=L$. The reason being that you can compute each oracle call yourself, using additional logarithmic space.
• 13.4k
Accepted

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

You don't have exponential time, what you have is a nondeterministic polynomial time machine. What you can try to do, in order to simulate the oracle call to $\mathcal{O}\in NP$ on a string $s$, is ...
• 13.4k
Accepted

### Existence of suitable pseudo-random number generators to derandomize BPP to P

$P^A\neq BPP^A$ implies the inexistence of strong enough PRG's in the relativized world, not necessarily in the usual (non black box) model. Remember that when defining a PRG, you require it to fool ...
• 13.4k

### Precise definition of oracle classes $A^B$

The simplest case is when $C$ has complete problems with respect to $\mathsf{F}B$ reductions (the function class corresponding to $B$). In that case, you can define $B^C$ as $B^L$ for some $C$-...
• 277k

### What is meant by an oracle separation between classes $\mathsf{BPP}$ and $\mathsf{BQP}$?

It depends. If $\mathrm{BPP} = \mathrm{BQP} = \mathrm{EXP} = \mathrm{EXP}^\mathrm{NP}$, then any oracle separation result would necessarily go beyond $\mathrm{ELEMENTARY} = \cup_{k} k-\mathrm{EXP}$. ...
• 2,275

### Oracle Relations Between Complexity Classes

You are right, but I think you have a misunderstanding about what is meant by an oracle separation result. There are two common kinds of oracle separation results that I've seen in complexity theory. ...
• 160k

### Do Oracles run in O(1) or O(n) time?

The oracle runs in a single step. Yes, it would take an ordinary Turing machine some number of steps to read the input but an oracle isn't an ordinary Turing machine – that's almost the ...
• 81.7k
Accepted

### Resource bounded reductions for RE-Complete problems

The reduction from $M$ to $HALT$ is essentially the function $x \mapsto \langle x, M\rangle$. This function can be computed very easily in linear time. $P^{HALT} = Exp^{HALT} = Rec^{HALT}$. The ...
• 22.2k
There are $2^{\aleph_0}$ possible oracles, but when fixing an oracle $A\subseteq \Sigma^*$, there are only countably many Turing machines $M^A$ with access to the oracle $A$. Remember that a Turing ...