Questions tagged [oracles]

The tag has no usage guidance.

22 questions
Filter by
Sorted by
Tagged with
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 ...
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?
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 ...
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-...
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 ...
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 ...
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 ...
24 views

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 ...
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

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