# Questions tagged [oracles]

The tag has no usage guidance.

23 questions
Filter by
Sorted by
Tagged with
9 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 ...
44 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?
27 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 ...
27 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-...
43 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 ...
31 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$ bits in $O(n^2)$ time as ...
43 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 ...
23 views

29 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 ...
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?
34 views

69 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?
### 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 ...
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 ...