Questions tagged [oracles]
The oracles tag has no usage guidance.
10
questions with no upvoted or accepted answers
4
votes
0
answers
381
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 ...
- 161
2
votes
0
answers
27
views
Special Properties for Oracles in HSP
Let $(G,+)$ be an abelian group, $X$ a finite set (of "colors"), and $f:G \to X$ a function such that there exists a subgroup $H<G$ for which $f$ separates cosets of $H$, i.e. $\forall a,...
- 722
2
votes
0
answers
73
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 ...
- 729
2
votes
0
answers
76
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 ...
- 2,881
1
vote
0
answers
47
views
Showing that a QBF in 3DNF form is in $NP^{NP}$
Consider the problem of checking whether a quantified Boolean formula of the form
$∃X_1 . . . ∃X_n ∀Y_1 . . . ∀Y_m \phi$,
for $\phi$ in $3DNF$ over $X_1, . . . , X_n, Y_1, . . . , Y_m$, is true.
I'm ...
- 423
1
vote
0
answers
66
views
How do we know that this Karp-Lipton theorem is derived from relativizing arguments?
Luca Trevisan wrote, " The oracle $C$ tells us that we cannot have a relativizing proof that derives the $𝑁𝑃 ⊈ 𝑃/𝑝𝑜𝑙𝑦$ conclusion from the $𝑃 ≠𝑁𝑃$ assumption, so a theorem such as Karp-...
- 729
1
vote
0
answers
15
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?
- 2,881
0
votes
0
answers
31
views
Is Quantum Search (SAT with only oracle access) NP-hard (and not NP-complete)?
Quantum search differs from the standard boolean SAT as it is restricted to only oracle calls to a circuit (or CNF formula). Where SAT gives us the structure of a formula (however loosely defined that ...
- 213
0
votes
0
answers
24
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 $\...
- 2,881
0
votes
0
answers
71
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 ...
- 313