# Questions tagged [oracles]

The tag has no usage guidance.

25 questions
Filter by
Sorted by
Tagged with
26 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$ ...
27 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 ...
1 vote
38 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 ...
1 vote
41 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 ...
1 vote
70 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
34 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
63 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-...
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 ...
1 vote
69 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 ...
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 ...
27 views

1 vote
44 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
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?
1 vote
38 views

1 vote
119 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 ...