Skip to main content
18 votes
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: ...
Arno's user avatar
  • 3,105
12 votes
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 ...
Sarvottamananda's user avatar
8 votes
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 ...
rus9384's user avatar
  • 1,632
8 votes

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 ...
Matt's user avatar
  • 181
7 votes

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 ...
David Richerby's user avatar
6 votes

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 ...
Yuval Filmus's user avatar
6 votes
Accepted

Oracle machine solving halting problem for other oracle machines

Remember that an oracle machine isn't really a "complete object" - basically anything interesting we might ask of it depends on what oracle we feed it. For example, whether an oracle machine $\Phi_e^-(...
Noah Schweber's user avatar
5 votes

Under what kind of oracles are $P$ and $NP$ equivalent?

It's not about strength: the Baker-Gill-Solovay nonrelativization result relativizes (hehehe), in the sense that for every $A$ there is a $B\ge_p A$ such that $\mathsf{P}^B\not=\mathsf{NP}^B$, and ...
Noah Schweber's user avatar
5 votes

Using hypercomputation for "impossible" problems?

Nope. Russell's paradox and the liar's paradox aren't undecidable. They aren't even decision problems. As far as we know, hypercomputers don't exist. They are an imaginary idea that don't appear ...
D.W.'s user avatar
  • 160k
4 votes
Accepted

Proving that the halting problem is not Turing-reducible to the acceptance problem for Turing machines

The two problems are equivalent up to many-one reductions. Reducing $\mathrm{Halt_{TM}}$ to $A_{\mathrm{TM}}$. Given a Turing machine $M$ and an input $w$, let $M'$ be the machine obtained from $M$ ...
Yuval Filmus's user avatar
4 votes
Accepted

Can a Turing machine be both decidable and undecidable relative to itself?

A Turing machine doesn't come with an oracle. The oracle comes from outside. Rather, an oracle Turing machine is a Turing machine that has a special way of accessing an oracle. When you run the Turing ...
Yuval Filmus's user avatar
4 votes

Complexity classes where $C^C = C$

This comment lists L (logspace), NC (polylog depth), P, BPP, BQP, and PSPACE as examples of self-low complexity classes.
tparker's user avatar
  • 1,096
4 votes
Accepted

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

Every language can be accepted by a Turing machine with an appropriate oracle, for example an oracle for the very language you want to accept. So if you understand "languages recognized by a Turing ...
Yuval Filmus's user avatar
4 votes

Show that the following language is undecidable

You haven't defined HALT, so let me assume that it consists of all Turing machines that halt on the empty input. If $M$ halts in time $f(n)$, then in particular it halts on the empty input, and so if $...
Yuval Filmus's user avatar
4 votes

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 ...
Bernardo Subercaseaux's user avatar
4 votes
Accepted

how does Kleene-Post show two languages that are not Turing reducible to each other?

Unfortunately, I don't possess a copy of Sipser, so I will just define all my notation. Let $T_0,T_1,\ldots$ an enumeration of all oracle Turing machines whose input is a word over some alphabet $\...
Yuval Filmus's user avatar
4 votes
Accepted

Does $A^B = A^C$ imply $B = C$?

Morally, yes, I agree. I believe what you write is correct and a reasonable way to think about things. You can stop reading here, but if you want to read longer musings/ramblings, continue on: ...
D.W.'s user avatar
  • 160k
3 votes
Accepted

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

Oracles have nothing to do with non-determinism. They are just a communication mechanism between the algorithm (or Turing machine) and an outside entity, the oracle $O$, which is just a language. In ...
Yuval Filmus's user avatar
3 votes
Accepted

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

A theorem about an oracle Turing machine $T^A$ (where $A$ is the oracle) is relativizing if it is of the form $$\forall A \,.\, \phi(T^A)$$ We say that the statement $\phi$ relativizes. There is no ...
Andrej Bauer's user avatar
  • 30.4k
3 votes

If we allow a database, what complexity class it is?

You can say anything you want, if you define your terms and your notation and make it clear what you are saying. In this case I would not expect someone to know what you mean by $M/f(n)$ or by $A \in ...
D.W.'s user avatar
  • 160k
3 votes

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.
Ariel's user avatar
  • 13.4k
3 votes
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 ...
Ariel's user avatar
  • 13.4k
3 votes
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 ...
Ariel's user avatar
  • 13.4k
3 votes

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$-...
Yuval Filmus's user avatar
3 votes

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}$. ...
Thinh D. Nguyen's user avatar
3 votes

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. ...
D.W.'s user avatar
  • 160k
3 votes

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 ...
David Richerby's user avatar
3 votes
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 ...
Kaveh's user avatar
  • 22.2k
3 votes
Accepted

Countably many oracle Turing machines?

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 ...
Ariel's user avatar
  • 13.4k

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