Questions tagged [oracles]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
10 views

Two definitions of oracle

There are two definitions of oracle a) Oracle is a black box that "knows" (in an instant) the answer to a given decision problem, such as is this number (presented e.g. as a binary string) a prime ...
4
votes
0answers
82 views

Is $\Sigma_2^{NP}=NP^{\Sigma_2}$?

Disclaimer: If not interested in my background, skip directly to the question below! I am a complete newbie when it comes to complexity theory. I come from a physics background and I am currently ...
1
vote
2answers
48 views

Why are Oracle Separations Counted as Evidence toward Unconditional Separation?

Particularly, we already have some oracle separation results such as $\mathbf{BPP}^A\neq \mathbf{BQP}^A$ [Simon], $\mathbf{NP}^A\not\subseteq \mathbf{BQP}^A$ [BBBV], and $\mathbf{BQP}^A\not\subseteq \...
1
vote
0answers
21 views

Is there any specific model/theory that proposes that the universe is an oracle machine? [closed]

Is there any specific (and well known/famous) model/theory that proposes that the universe is an oracle machine? Physicist Roger Penrose said his book "The Shadows of the Mind" It would be just as ...
1
vote
0answers
8 views

$NC$ and $FNC$ oracles low for functional and Stockemeyer classes respectively?

We know $P^{NC}=P$ and $FP^{FNC}=FP$ hold. Do $FP^{NC}=FP$ and $P^{FNC}=P$ hold?
1
vote
1answer
33 views

Manipulating Intersection of oracles

Suppose for different classes $A,B,C$ we have that $A\subseteq P^B$ and $A\subseteq P^C$. We have $A\subseteq P^{B}\cap P^{C}$. Does it also mean $A\subseteq P^{B\cap C}$? Supposing $A\subseteq P^{B\...
0
votes
0answers
21 views

On query equally powerful oracles?

If $\mathcal C=\mathcal D$ then does $\mathcal A^\mathcal C=\mathcal A^\mathcal D$ hold ($\mathcal C^A=\mathcal D^A$ need not hold)? The class $\mathcal A$ could query same for $\mathcal C$ and $\...
1
vote
2answers
52 views

$P/poly$ as oracle to itself?

How can we show $P/poly^{P/poly}=P/poly$? What tricks are generally used for self lowness of a class such as $BPP$, $SPP$ etc?
0
votes
0answers
62 views

Showing if $A\in DSPACE(n^c) \text{ or } DTIME(n^c)$ then $EXP^A \neq EXP$ and $EXP^A= EXP$

If a language $A\in DSPACE(n^c)$, then $EXP^A\neq EXP$ If a language $A\in DTIME(n^c)$, then $EXP^A= EXP$ What I tried: Since it's impossible to show that $EXP \subseteq EXP^A$ because: We ...
1
vote
0answers
67 views

On oracle access containment?

If $X,Y$ are complexity classes in the polynomial hierarchy with $X\subseteq Y$. With abuse of notation assume $X,Y$ also as the TMs that accept languages in classes $X,Y$ respectively. Then is it ...