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

14 questions
Filter by
Sorted by
Tagged with
1k views

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 ...
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$: ...
462 views

### Is relativization well-defined?

According to BGS theorem , 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$ ...
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 ...
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. ...
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 ...
480 views

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 ...
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$...
### 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}$?