Questions tagged [oracles]

The tag has no usage guidance.

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

Learning algorithms- difference between a learner (the algorithm) having continuous access to the samples (oracle) vs getting all at start

Is there any fundamental difference between learning algorithms e.g. variants of PAC which have continuous access to examples on which to train (i.e. these are obtained as the algorithm runs, when ...
1
vote
1answer
49 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?
1
vote
1answer
29 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 ...
1
vote
0answers
36 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-...
2
votes
1answer
49 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 ...
0
votes
3answers
47 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 ...
0
votes
2answers
48 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 ...
2
votes
0answers
24 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,...
2
votes
1answer
55 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, ...
2
votes
1answer
37 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 ...
2
votes
1answer
53 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
50 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 ...
0
votes
1answer
241 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
250 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
155 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
37 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
9 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
34 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
23 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
71 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
64 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
68 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 ...