# Questions tagged [oracles]

Questions regarding oracle machines in computational complexity theory. Oracles can serve as an indicator that a separation between complexity classes is beyond the scope of certain proof techniques.

80 questions
Filter by
Sorted by
Tagged with
97 views

### Possibility of hierarchy with $UP$ class?

I am not sure if this is a cheap query. However I am unable to find this myself. So I am posting here. The standard complexity class is built with $NP$ and $coNP$ and leads up to $PSPACE$. The ...
109 views

### Oracle separation between PH and PSPACE

I am having difficulty understanding the concept and intuition behind this proof. The proof deals with constructing an oracle $A$ relative to which $PH$ is separated from $PSPACE$. I have several ...
121 views

### Lower bound on alternations needed in $BQP$ versus $PH$ result?

What is the fastest $f(n)$ the relatively new result of oracle separation of $\mathsf{BQP}$ from $\mathsf{PH}$ provides such that ${\#\mathsf{SAT}}\not\subseteq\mathsf{FP}^{\mathsf{PH}[O(f(n))]}$ ...
112 views

### Why is the “general notion of a reduction […] inherent to the notion of self-reducibility”?

While reading "Computational Complexity: A Conceptual Perspective" by Oded Goldreich, I have come across the following passage, which I simply cannot get my head around: Note that the general ...
116 views

### Can relativization technique be applied to natural NP-complete languages?

Levin  defined distNP is the distributional problem (L,D), where L ∈ NP, and D is an ensemble of efficiently samplable distributions over problem instances. We say that a distNP problem (L,D) is ...
334 views

### Indications that strengthen the conjecture: NEXP ⊊ EXP^NP

I am trying to find indications that strengthen the conjecture of NEXP ⊊ EXP^NP. Clearly NEXP ⊆ EXP^NP, and there are some hints that this inclusion is proper. Some Examples: 1. A paper by Shuichi ...
55 views

### An alternative characterization of some NExp-Time Turing machine with oracles

Let me denote by $\Sigma_i^P$ be a class from i-th level of polynomial time hierarchy (see eg. PH). I'm interested in the following type of a Turing Machine $\mathcal{M}$: $\mathcal{M}$ is ...
84 views

### Partitioning a square for optimal queries

I have a square plate of size 1x1, full of lots of skittles. I want to eat all of the skittles, but the only way I can get the skittles is through these two oracles: $f(x, y, r)$ tells me how many ...
212 views

104 views

187 views

### How to prove $P^{Halt} = PSPACE^{Halt}$ [closed]

Halt means the halting set. $PSPACE^{Halt}$ is the class of problems that can be solved with polynomial memory (possibly exponential time), given a halting oracle.
162 views

### What are examples of complexity classes that have contradictory relativizations but they were proven to be either equal or unequal?

In this article Chang et al. provide a counterexample by giving an oracle $A$ such that $\mathsf{IP}^A \neq \mathsf{PSPACE}^A$. I wanted to know if there are more examples like this.
398 views

### Compressing information about the halting problem for oracle Turing machines

The halting problem is well-known to be uncomputable. However, it is possible to exponentially "compress" information about the halting problem, so that decompressing it is computable. More precisely,...
191 views

### Oracle comparing $EXP$ with $UP$

Heller (Theorem 6) gave an oracle relative to which $NP=EXP$, and Homer & Selman gave an oracle relative to which $P=UP$ and $\Sigma_2^P=EXP$. Beigel, Buhrman, Fortnow (freely available author's ...
107 views

684 views

A recent question asks whether relativization is well-defined. This question wonders how to put one use of it on firmer ground. In the BGS 1975 proof that there exists a language $B$ such that $... 1answer 637 views ###$\mathsf{NP} \cap \mathsf{coNP}$as oracle Does$\mathsf{NP^{NP \,\cap\, coNP}=NP}$hold? Clearly$\mathsf{NP^{NP}\neq NP}$, but it seems to me that$\mathsf{NP\cap coNP}$is "deterministic" which makes me believe this is true. Is there a ... 2answers 417 views ### Is relativization well-defined? According to BGS theorem , there is an oracle$A$such that$P^A\neq NP^A$. If the relativization operation$B\mapsto B^A$was a well-defined function, one would expect that from$B^A\neq C^A$... 0answers 102 views ### Reduction from a geometric decision problem to its maximization problem I am interested in the following NP-complete decision problem: ... 1answer 205 views ### Oracles which put integer factorization in P I'm compiling a list of as many problems (decision or function) as I can find such that, if I had an oracle that could solve the problem in P, then integer factorization would also be in P. Here is a ... 1answer 501 views ### Relativized world where${\bf P^A}={\bf NP^A}\not = {\bf PP^A}$I would like to know if there exists a relativized world where${\bf P^A}={\bf NP^A}\not = {\bf PP^A}$. I am also interested to know if there exists a relativized world where${\bf P^B} \not = {\bf NP^...
870 views

I am a physicist getting acquainted with one of the typical constructs for formulation and analysis of quantum algorithms (such as search problems or query complexity models), namely the "oracle ...
506 views

### $\mathsf{P}^\mathsf{BPP}$ vs $\mathsf{BPP}$ (Are they known to be equal)

Is it known if $\mathsf{P}^\mathsf{BPP}= \mathsf{BPP}$ ? It's clear that $\mathsf{BPP} \subseteq \mathsf{P}^\mathsf{BPP}$. Now, since $\mathsf{BPP}$ is closed under complementation, union, and ...
78 views

### Natural relativized worlds

The oracles that are used in relativized collapses or separations of complexity classes rarely represent $natural$ algorithmic problems. They are typically constructed "artificially" with techniques ...
411 views

### What is $DTIME(n^a)^{DTIME(n^b)}$?

This might be embarrassing, but it turned out I don't know what is $DTIME(n^a)^{DTIME(n^b)}$. It is between $DTIME(n^{ab})$ and $DTIME(n^{a(b+1)})$ but where? Update: There are three possible ways to ...