Questions tagged [oracles]
The oracles tag has no usage guidance.
25
questions
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
3
votes
2
answers
279
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 \...
- 271
2
votes
1
answer
57
views
Is $A \leqslant_P B \iff A \in \mathsf{P}^B$? If not are there counter-examples?
The way I think of reducing problem $A$ to problem $B$ in polynomial time, i.e. $A \leqslant_P B$, is that you assume an efficient solution to $B$ which is enough to solve $A$. Now, this is ...
2
votes
1
answer
81
views
For all oracles A, If $P^A \neq PSPACE^A$, then Does it imply that $P \neq PSPACE$?
My question related to relativized world. I would like to know about how to show that class is different from another class in the oracle world and whether this applied to our real world.
For example, ...
- 729
2
votes
1
answer
40
views
Oracle query’s required
The variables $a,b,c \in \{0,1\}$, thus $a^k, b^k, c^k \in \{0,1\}$
I want to pass a query to an oracle that returns the coefficients of each term $(1,a,b,c,ab,ac,bc,abc)$ in the expansion of ...
- 201
2
votes
1
answer
58
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 ...
- 201
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
1
answer
76
views
Does $NP^{SAT}=NP^{NP}$?
Does $NP^{SAT}=NP^{NP}$?
We can see easily that $NP^{SAT}\subseteq NP^{NP}$, because $SAT \in NP$.
But is the other side $NP^{NP}\subseteq NP^{SAT}$ also true? If yes, how can we prove it?
- 123
1
vote
4
answers
73
views
Can quantum computers be modelled as a classical computer with access to an oracle?
Quantum computers can solve certain problems faster than classical computers e.g factoring numbers.
and this is because quantum computers can do a fourier transform on $n$ qubits in $O(n^2)$ time as ...
- 91
1
vote
1
answer
39
views
Making statements about quantum complexity theory
It is my understanding, based on this question that problems solved on quantum computers with oracles don’t make any statements about BQP in relation to other complexity classes.
The fallacy is in ...
- 11
1
vote
1
answer
35
views
How to define the languages of the implicit set system problems?
There are implicit versions of some set system problems or matroid problems.
A set system is a pair $(U, \mathcal{F})$, where $U$ is a universe of size $n$ and $\mathcal{F}$ is a collection of susbets ...
- 623
1
vote
1
answer
38
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\...
- 2,881
1
vote
2
answers
129
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?
- 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
45
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 ...
- 11
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
1
answer
324
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 ...
- 21
0
votes
2
answers
62
views
Oracle that can only definitively say if an instance is unsatisfiable
Assuming I have an Oracle that takes as input a strictly 3SAT Boolean instance and states whether the instance is satisfiable or not. If it says instance is unsatisfiable then the instance is ...
- 25
0
votes
1
answer
31
views
Is there an oracle $A$ with $P^A = NP^A$, but $EXP^A \not= NEXP^A$?
Is there an oracle $A$ with $P^A = NP^A$, but $EXP^A \not= NEXP^A$ ?
I found a proof with padding arguments (wikipedia), that
$$ P = NP \Rightarrow EXP = NEXP $$
If an oracle $A$ exists with $P=NP$ ...
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