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.

Filter by
Sorted by
Tagged with
12
votes
2answers
1k views

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

By http://www.cs.umd.edu/~jkatz/complexity/relativization.pdf If $A$ is a PSPACE-complete language, $P^{A}=NP^{A}$. If $B$ is a deterministic polynomial-time oracle, $P^{B}\ne NP^{B}$ (assuming $P\...
8
votes
2answers
827 views

Baker Gill Solovay $P^B \ne NP^B$ relativization, what class is $B$ in?

A recent question asks whether relativization is well-defined. This question wonders how to put one use of it on firmer ground. In the BGS 1975 proof that there exists a language $B$ such that $...
20
votes
3answers
483 views

space-bounded TMs and oracles

In general, the query-tape for an oracle counts towards the space-complexity of a TM. However, it seems plausible to allow a write-only oracle-tape (such as is used in L-space reductions). Is such a ...
19
votes
5answers
999 views

P with integer factorization oracle

I just read the "Is integer factorization an NP-complete problem?" question ... so I decided to spend some of my reputation :-) asking another question $Q$ having $P(\text{Q is trivial}) \approx 1$: ...
8
votes
2answers
462 views

Is relativization well-defined?

According to BGS theorem [1], there is an oracle $A$ such that $P^A\neq NP^A$. If the relativization operation $B\mapsto B^A$ was a well-defined function, one would expect that from $B^A\neq C^A$ ...
29
votes
1answer
1k views

Are there canonical non-relativizing techniques?

In a lot of domains, there are canonical techniques which everybody working in the field should master. For example, for logspace reductions, the "bit trick" for composition consisting of not ...
8
votes
2answers
374 views

Relativization with Respect to Non-Recursive Oracles

In the paper Relativizations of the P = ? NP Question, Baker et al. showed that there are relativized worlds in which either P = NP or P ≠ NP holds. All oracles in their settings were recursive sets. ...
14
votes
3answers
573 views

Complexity theory when an oracle is part of the input

The most common way in which oracles occur in complexity theory is as follows: A fixed oracle is made available to, say, a Turing machine with certain limited resources, and one studies how the oracle ...
12
votes
1answer
480 views

Does Kannan's theorem imply that NEXPTIME^NP ⊄ P/poly?

I was reading a paper of Buhrman and Homer “Superpolynomial Circuits, Almost Sparse Oracles and the Exponential Hierarchy”. On the bottom of page 2 they remark that the results of Kannan imply that $...
7
votes
4answers
400 views

Complexity class separation in the presence of relativization barriers

Give an example of complexity classes $M$ and $N$ and oracles $A$ and $B$ such that 1. $M^A=N^A$ and 2. $M^B\neq N^B$ and 3. $M \neq N$.
12
votes
1answer
458 views

Oracle relative to which $\mathsf{BPP}$ is not contained in $Δ_2 \mathsf{P}$

Complexity Zoology by Greg Kuperberg states that there is a language $X$ such that $\mathsf{BPP}^X \nsubseteq \mathsf{\Delta_2 \mathsf{P}}^X$ — in other words, $\mathsf{BPP}^X \nsubseteq \mathsf{P}^{\...
1
vote
1answer
202 views

Can an oracle allowing errors be non-relativizing?

I am experimenting with k-SAT. I'm using an oracle that returns the total number of satisfiable truth assignments, which is in #P. The interest here is that this total is returned modulo a natural ...
1
vote
1answer
107 views

Is predicting (in the limit) computable sequences as hard as a dominating function?

Define a "predicting oracle" to be an oracle that does as described in this question. default (weak) version: Is it the case that, for every predicting oracle $O$, there exists an oracle machine $M$...
1
vote
1answer
699 views

Is $P^{\#P}=(P^{\#P})^{\#P}$ ?

Intuitively, this equation holds because given the second #P oracle can be omitted since we can always use the first one. More generally, say O is an oracle, is $P^{O}= (P^{O})^{O}$?