# Questions tagged [oracles]

Questions regarding oracle machines in computational complexity theory. Oracles can serve as an indicator that a separation between complexity classes is beyond the scope of certain proof techniques.

98 questions
Filter by
Sorted by
Tagged with
1 vote
56 views

### Is NLOGTIME self-low?

https://en.wikipedia.org/wiki/Low_(complexity) Every class which is low for itself is closed under complement, provided that it is powerful enough to negate the boolean result. EXP, which is closed ...
• 111
200 views

### Relativized world in which P ≠ NP = coNP

Do we know of an oracle relative to which P ≠ NP but NP = coNP?
• 547
168 views

### Can the ellipsoid method be used with a randomized separation oracle?

Suppose we are trying to solve the following optimization problem: $$\text{maximize } ~~ c\cdot y \\ \text{subject to } ~~ y\in S$$ where the region $S$ is described by an exponential number of ...
79 views

### Is complexity class containment preserved relative to any oracle?

That is, suppose $A\subseteq B$ for two complexity classes $A$ and $B$. Is it the case that for any oracle $C$, and any definitions $A^*$ and $B^*$ of $A$ and $B$, we have ${A^*}^C\subseteq {B^*}^C$? (...
132 views

• 3,221
1 vote
70 views

• 12.6k
1 vote
86 views

• 304
8k views

### Oracle Construction for Grover's Algorithm

In Mike and Ike's "Quantum Computation and Quantum Information", Grover's algorithm is explained in great detail. However, in the book, and in all explanations I have found online for Grover's ...
• 331
396 views

### Does there exist an oracle $A$ such that $(P^{\#P})^{A} \neq PSPACE^{A}$?

Background We know that $P^{\#P} \subseteq PSPACE$. In addition, we known from Toda's theorem that $PH \subseteq P^{\#P}$. For more background on $\#P$, see here: https://en.wikipedia....
• 5,005
782 views

### What is the minimum complexity oracle that separates PSPACE from the polynomial hierarchy?

Background It is known that there exists an oracle $A$ such that, $PSPACE^A \neq PH^A$. It is even known that the separation holds relative to a random oracle. Informally, one may interpret ...
• 5,005
262 views

### Using an oracle to find a vector $b$ for which $Ax=b$ has a solution

There is an oracle built around a hidden $m\times n$ matrix $A$ all of whose entries are 0 or 1, where $m>n$. The oracle takes as input an integer vector $b$ with positive entries, and answers as ...
849 views

### Is $\sf{P^{NP \cap coNP}} = \sf{NP \cap coNP}$?

If it is unknown, are there reasons to believe that they might not be equal?
• 137
174 views

### SETH-like hypothesis for machine with oracle access to some level of PH

I am wondering if hypothesis such as Strong Exponential Time Hypothesis (SETH) have been studied for problems being in a higher level of the polynomial hierarchy when we give the machine access to an ...
• 2,049
437 views

### Oracle separating $coNP$ and $NP/poly$

I'd like to prove that, with respect to some adversarial oracle $O$, $coNP^O \not\subseteq NP/poly^O$. I was thinking of using $\textsf{UNSAT}$ for this and to build my oracle as follows: $O$ will "...
• 137
196 views

### Oracles for sub-exponential circuit complexity of $\Sigma_2 EXP$

Couldn't find this one anywhere... It's an open problem whether $\Sigma_2 EXP$ problems have exponential-size circuit complexity. Is there an oracle relative to which $\Sigma_2 EXP$ has $2^{o(n)}$ ...
• 26.7k
152 views

### An oracle in $\mathsf{NEXP}$ that separates ZPP from BPP

Does there exist an oracle $A \in \mathsf{NEXP}$ such that $\mathsf{ZPP}^A \neq \mathsf{BPP}^A$?
190 views

### Given oracle for Max-3SAT compute clauses that cannot be satisfied

We know that Max-3SAT is NP-hard to compute exactly (and also hard to approximate to a particular constant multiplicative factor). However, suppose you are given an oracle for Max-3SAT that tells you ...
492 views

### Is there a good notion of non-termination and halting proofs in type theory?

Constructive type theory with its basic interpretation under the curry howard correspondence consists only of total, computable functions. In the literature, some has been said on using "computational ...
158 views

### Oracle-Decidability of Algebraic Independence

Consider numbers $x_1,...,x_n\in \mathbb{R}$ given by TMs $M_1,...,M_n$ such that $M_i$ approximates $x_i$ to an arbitrary precision (by allowing it to run longer and longer). I am interested in the ...
• 5,501
147 views

### Lower bounds for nonuniform circuits and oracles separating complexity classes

I have read that Furst, Sax, and Sipser came up with their lower bound for nonuniform AC0 while trying to prove an oracle separation. Can someone explain how proving lower bounds for circuits and ...
• 4,001