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.

82 questions
Filter by
Sorted by
Tagged with
59 views

Turing meta-oracle

Let H(P) be some program that given P('s source code) computes whether or not P terminates, i.e. solves the halting problem. H only needs to terminate if P terminates. (This disallows solutions like ...
186 views

Results comparing BQP and NEXP

Are there oracle results with $$P=NP\neq BQP=NEXP\mbox{ and }P=NP\neq BQP\neq NEXP?$$ Also is there a $PCP$ characterization of $BQP$ like $$PCP(O(poly(n)),1)=PCP(O(poly(n)),O(poly(n)))=NEXP?$$
152 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 ...
116 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 ...
128 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))]}$ ...
114 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 ...
119 views

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

Levin [1] 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 ...
340 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 ...
58 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 ...
85 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 ...
234 views

109 views

197 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.
165 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.
415 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,...
197 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 ...
110 views

770 views

884 views

Quantum oracle implementation overhead

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 ...
518 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 ...
81 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 ...
415 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 ...
Is $\mathsf{MA}$ equal to $\mathsf{NP}^\mathsf{RP}$?
I haven't been able to find a statement relating $\mathsf{MA}$ and $\mathsf{NP}^\mathsf{RP}$ in the literature; pointers would be appreciated. I believe they are equal: \$\mathsf{MA} \subseteq \...