Questions tagged [oracles]
The oracles tag has no usage guidance.
25
questions
0
votes
1
answer
42
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
37
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 ...
- 243
1
vote
1
answer
42
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
0
answers
57
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 ...
- 443
1
vote
1
answer
78
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
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
0
answers
68
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
2
votes
1
answer
60
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 ...
1
vote
4
answers
78
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
0
votes
2
answers
63
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
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,...
- 742
2
votes
1
answer
93
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
59
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
81
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
0
votes
1
answer
361
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
4
votes
0
answers
395
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
303
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
1
vote
0
answers
47
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,891
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,891
0
votes
0
answers
26
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,891
1
vote
2
answers
134
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,891
0
votes
0
answers
73
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
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,891