The oracles tag has no wiki summary.
10
votes
1answer
244 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
155 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 ...
2
votes
1answer
218 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
54 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
323 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 ...
9
votes
1answer
307 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
114 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
473 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
210 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
245 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
0answers
45 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 ...
14
votes
1answer
297 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
368 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
232 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 ...
-1
votes
1answer
132 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
180 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 ...
11
votes
1answer
312 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 ...
13
votes
3answers
365 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
143 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
329 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
255 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
203 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 ...
7
votes
4answers
444 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
269 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
376 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 ...
1
vote
1answer
455 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
172 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 ...
9
votes
2answers
369 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 ...
24
votes
1answer
506 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
297 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
186 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
420 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
341 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 ...
1
vote
2answers
735 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 ...
11
votes
1answer
423 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 ...
6
votes
4answers
290 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
238 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
332 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 ...
