Questions tagged [oracles]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
1answer
33 views

Algorithm for idempotent algebra

A boolean algebra expression can be converted into an idempotent algebra using $$\bar a \equiv 1-a, \qquad a \vee b \equiv a+b -ab, \qquad a \wedge b \equiv a \otimes b$$ where $\otimes$ is the ...
2
votes
0answers
19 views

What does it mean this relation: $BQP^{BQP} = BQP$

I am reading this paper by Fortnow, titled: One Complexity Theorist's View of Quantum Computing. In section 4, he states the following: Bernstein and Vazirani [BV97] show that BQP can simulate any ...
-1
votes
1answer
150 views

Baker, Gill, Solovay - construction of oracle B such that P^B != NP^B

I have some questions about Baker, Gill, Solovay proof of the existence of an oracle such that P^B != NP^B. The proof can be found in Siam Journal of Computing, 4:432-442, 1975 [219]. Why Isn't this ...
4
votes
0answers
92 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
57 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
22 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
53 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
63 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 ...