17 votes

Are there any existing problems that wouldn't be solvable with a halting oracle?

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 ...
user avatar
13 votes

Complexity classes where $C^C = C$

$\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}} = ...
user avatar
  • 201
13 votes
Accepted

Why is this argument for $P\neq NP$ wrong?

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 ...
user avatar
  • 4,009
12 votes
Accepted

Why is Oracle Turing Machine important?

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 ...
user avatar
  • 140k
12 votes

How is it valid to use oracles in mathematical arguments?

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 ...
user avatar
10 votes

How is it valid to use oracles in mathematical arguments?

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 ...
user avatar
  • 16.1k
9 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 ...
user avatar
  • 4,697
8 votes
Accepted

Why are non-relativizing proofs preferred to relativizing ones?

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/...
user avatar
8 votes
Accepted

Confusion about the Time Hierarchy Theorem and relativization

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 ...
user avatar
  • 11.9k
8 votes
Accepted

How does the use of oracle Turing machines not lead to contradictions?

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 ...
user avatar
  • 29.1k
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 ...
user avatar
  • 1,349
7 votes

Can oracle arguments separate P and NP?

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}$. ...
user avatar
  • 11.9k
7 votes
Accepted

Is it axiomatic that the Time Hierarchy Theorem holds true in all relativized worlds?

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 ...
user avatar
6 votes

How is it valid to use oracles in mathematical arguments?

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 ...
user avatar
  • 19.1k
6 votes

Complexity classes where $C^C = C$

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.
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 ...
user avatar
6 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 ...
user avatar
5 votes

Is it allowed to do a binary search with an oracle when proving NP-completeness?

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, ...
user avatar
  • 140k
5 votes
Accepted

Is it allowed to do a binary search with an oracle when proving NP-completeness?

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. ...
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.
user avatar
  • 934
4 votes

The meaning of relativization

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 ...
user avatar
  • 140k
4 votes
Accepted

Constructing solution to 3SAT formulas using oracle queries

You have the right idea. Suppose you have a SAT oracle and an instance $I$ of 3SAT (or whatever SAT-ish class you like) containing $n$ variables, $x_1, x_2, \dotsc x_n$. You could then do this: ...
user avatar
  • 14.5k
4 votes

Why is Oracle Turing Machine important?

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 ...
user avatar
4 votes
Accepted

Polynomial hierarchy: inclusion between spaces

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} = \...
user avatar
  • 4,697
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 ...
user avatar
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 ...
user avatar
4 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^-(...
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 $...
user avatar

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