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.

learn more… | top users | synonyms

15
votes
2answers
408 views

For a random oracle R, does BPP equal the set of computable languages in P^R?

Well, the title pretty much says it all. The interesting question above was asked by commenter Jay on my blog (see here and here). I'm guessing both that the answer is yes and that there's a ...
9
votes
0answers
187 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 ...
5
votes
2answers
268 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 ...
12
votes
1answer
279 views

$\mathsf{NP} \cap \mathsf{coNP}$ as oracle

Does $\mathsf{NP^{NP \,\cap\, coNP}=NP}$ hold? Clearly $\mathsf{NP^{NP}\neq NP}$, but it seems to me that $\mathsf{NP\cap coNP}$ is "deterministic" which makes me believe this is true. Is there a ...
6
votes
2answers
236 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$ ...
4
votes
0answers
89 views

Reduction from a geometric decision problem to its maximization problem

I am interested in the following NP-complete decision problem: ...
4
votes
1answer
172 views

Oracles which put integer factorization in P

I'm compiling a list of as many problems (decision or function) as I can find such that, if I had an oracle that could solve the problem in P, then integer factorization would also be in P. Here is a ...
10
votes
1answer
349 views

Relativized world where ${\bf P^A}={\bf NP^A}\not = {\bf PP^A}$

I would like to know if there exists a relativized world where ${\bf P^A}={\bf NP^A}\not = {\bf PP^A}$. I am also interested to know if there exists a relativized world where ${\bf P^B} \not = {\bf ...
2
votes
2answers
281 views

Quantum oracle implementation overhead

I am a physicist getting acquainted with one of the typical constructs for formulation and analysis of quantum algorithms (such as search problems or query complexity models), namely the "oracle ...
3
votes
1answer
294 views

$\mathsf{P}^\mathsf{BPP}$ vs $\mathsf{BPP}$ (Are they known to be equal)

Is it known if $\mathsf{P}^\mathsf{BPP}= \mathsf{BPP}$ ? It's clear that $\mathsf{BPP} \subseteq \mathsf{P}^\mathsf{BPP}$. Now, since $\mathsf{BPP}$ is closed under complementation, union, and ...
2
votes
1answer
63 views

Natural relativized worlds

The oracles that are used in relativized collapses or separations of complexity classes rarely represent $natural$ algorithmic problems. They are typically constructed "artificially" with techniques ...
6
votes
2answers
365 views

What is $DTIME(n^a)^{DTIME(n^b)}$?

This might be embarrassing, but it turned out I don't know what is $DTIME(n^a)^{DTIME(n^b)}$. It is between $DTIME(n^{ab})$ and $DTIME(n^{a(b+1)})$ but where? Update: There are three possible ways to ...
10
votes
1answer
344 views

Is $\mathsf{MA}$ equal to $\mathsf{NP}^\mathsf{RP}$?

I haven't been able to find a statement relating $\mathsf{MA}$ and $\mathsf{NP}^\mathsf{RP}$ in the literature; pointers would be appreciated. I believe they are equal: $\mathsf{MA} \subseteq ...
0
votes
0answers
118 views

Oracle that will provide any computable information about another oracle

Suppose I have an oracle X. Then let Y be an oracle which will answer any computable question about X. In other words, Y takes as input a Turing program which can in turn make calls to X. Y then ...
8
votes
4answers
628 views

Oracle results on P vs BPP

Let $A$ be any EXP complete problem. Then, $P^A = NP^A$. Let $B$ be some oracle that takes into accounts the queries that $M$ (a TM in P) will make, and we can get $P^B \neq NP^B$. Question: Do we ...
6
votes
2answers
239 views

Oracle complexity of a problem in the Counting Hierarchy

In "On The Complexity of Numerical Analysis" (SIAM J. Comp. Vol. 38, 2009), Allender et al. introduce the problem of PosSLP and show that its complexity lies in the counting hierarchy, and more ...
-3
votes
1answer
333 views

complexity of SAT with NP oracle

I have a SAT formula, but each propositional variable corresponds to an NP-C problem. Namely, in order to say whether the assignment of a variable is true or false, one has to consult an NP oracle. ...
1
vote
1answer
84 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 ...
15
votes
2answers
351 views

Reconstructing a tree from separator queries

Suppose $T$ is an constant-degree tree whose structure we do not know. The problem is to output the tree $T$ by asking queries of the form: "Does the node $x$ lie on the path from node $a$ to node ...
5
votes
0answers
392 views

Can we show that $\mathsf{NL}^\mathsf{NL} = \mathsf{NL}$? [closed]

We know by Immerman–Szelepcsényi theorem that $\mathsf{NL}=\mathsf{coNL}$? Does it follow from this theorem that $\mathsf{NL}^\mathsf{NL} = \mathsf{NL}$? Here, $\mathsf{NL}^\mathsf{NL}$ denotes the ...
1
vote
1answer
256 views

Concerning decidability of a problem on real numbers [closed]

This question is an outgrowth of a certain maths problem I've been thinking about. Suppose you use an oracle to represent a real number. The oracle is of the following form: you give it an integer ...
0
votes
1answer
150 views

What is known about NP hard problems that access preprocessed information?

Please accept my apologies ahead of time since I fear that this isn't an adequate question for cstheory. I plan on releasing my ideas to get feedback, but I don't know if my target audience will ...
1
vote
1answer
187 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 ...
12
votes
1answer
352 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 ...
14
votes
3answers
442 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 ...
6
votes
0answers
156 views

Oracle sparating FIP for bounded-depth Frege from FIP for Frege (and hardness conditions on DDH)

Is there an oracle such that in the relativized world, bd-Frege (bounded depth Frege propositional proof system) has FIP (feasible interpolation property) but Frege does not have FIP? Such an ...
6
votes
2answers
339 views

Is $PP^{(PP^A)} = PP^A$ ?

I've looked in the Zoo and it seems it is not true because $PH \subseteq P^{PP}$. Nonetheless I've passed by a paper that appears to have used a positive result. It was in the context that $f : ...
5
votes
1answer
321 views

Is there an oracle that separates two complexity classes known to be equal?

We know that there exist two oracles $A$ and $B$ such that $P^A=NP^A$ and $P^B\neq NP^B$, this implies the obstacle of proving $P\neq NP$ using diagonalization. I just wonder if there exist two ...
6
votes
0answers
242 views

Oracle complexity classes and hardness under different notions of reduction

Let C be a complexity class, and let L be a language such that PC ⊆ PL. Then it’s natural (and easy to prove) that L is C-hard with respect to Cook reductions (polytime Turing reductions). This ...
13
votes
5answers
619 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$: ...
5
votes
2answers
292 views

Dominations under oracles which is closed under complement?

Edited at 2010/11/29: As John Watrous have mentioned, the class $\mathsf{C^O}$ may be not well-defined. After reading some early posts, I try to restate my question in an unambiguous way. Let ...
1
vote
2answers
405 views

When we are using Random Oracle Model

There are protocols which make use of invoking an oracle or submitting queries to an oracle and getting response from that. There are many examples in which oracles are used to define security, like ...
11
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 ...
0
votes
1answer
594 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}$?
3
votes
0answers
176 views

Reference Request: Oracle applications outside cryptography

Oracles have been used to prove results in cryptography where all parties have access to a random oracle instantiated with some cryptographic primitive. I am looking for references to papers that have ...
10
votes
2answers
411 views

Are Oracles Associative?

This question may have an obvious answer ... but here's the question anyway. Intuitively, it is the following plausible statement - "a machine with a subroutine A which in turn has a subroutine B is ...
27
votes
1answer
732 views

Are there canonical non-relativizing techniques ?

In a lot of domains, there are canonical technics which everybody working on the field should master. For example, for logspace reductions, the "bit trick" for composition consisting of non ...
8
votes
2answers
318 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. ...
9
votes
1answer
196 views

Worlds Relative to Which “Invulnerable Generators” Do Not Exist

Invulnerable generators are defined as follows: Let $R$ be an NP relation, and $M$ be a machine which accepts $L(R)$. Informally, a program is an invulnerable generator if, on input $1^n$, it ...
6
votes
1answer
474 views

Oracle relative to which BPP = EXP

An oracle construction relative to which BPP = EXP is usually attributed to Heller (Mathematical System Theory Vol. 17, 1984). Unfortunately I don't have the paper available in my library. Could ...
13
votes
2answers
373 views

Exhausting Simulator of Zero-Knowledge Protocols in the Random Oracle Model

In a paper titled "On Deniability in the Common Reference String and Random Oracle Model," Rafael Pass writes: We note that when proving security according to the standard zero-knowledge ...
2
votes
2answers
1k views

Using decision version of TSP to solve optimization version

Given an oracle for solving the decision version of TSP, how would I use this to solve the optimization version of TSP. This is not a homework assignment, but of general interest. I have been trying ...
12
votes
1answer
476 views

Circuits with oracles vs. Turing Machines with oracles

Put simply: what is the correspondance between Turing machines with oracles, and uniform circuit families with oracles? How are the latter defined in order to obtain the same computational model, for ...
7
votes
4answers
318 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$.
9
votes
2answers
246 views

Is there a definitive reference for Turing machines with multiple oracle tapes?

Most of the literature seems to be concerned with machines with single oracles for specific problems, however there appear to be a few papers that consider machines with multiple oracles. Is there a ...
14
votes
3answers
351 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 ...