# Tagged Questions

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.

53 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 ...
183 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 ...
48 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 ...
111 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 ...
71 views

### Functional oracles

In the traditional oracle Turing machine, the oracle is specified as a decision problem. Roughly speaking, one puts a string in the oracle tape, and asks whether it is true or false. I am wondering ...
119 views

### Manuel's trick and oracle separation

Impagliazzo gave a talk last week at Simons Institute on oracle separation. At minute 5:34 he asks whether a one-way permutation can be constructed given oracle access to a random function oracle. ...
508 views

### What are consequences of the collapse of CH?

I don't grasp the full complexity of the counting hierarchy $CH$. I understand $CH$ is in $PSPACE$, and contains $PH$ within its second level, due to the Toda's theorem. But, what would be important ...
674 views

### Is there an oracle such that SAT is not infinitely often in sub-exponential time?

Define $io$-$SUBEXP$ to be the class of languages $L$ such that there is a language $L' \in \cap_{\varepsilon > 0} TIME(2^{n^{\varepsilon}})$ and for infinitely many $n$, $L$ and $L'$ agree on all ...
169 views

### An oracle relative to which EXP(NP) = BPP

Whether or not $\mathbf{BPP} = \mathbf{EXP}^{\mathbf{NP}}$ is an open problem, although we believe the former is strictly contained in the other. I guess, from the absence of the proof of the ...
511 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 ...
225 views

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 $... 2answers 380 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 ... 1answer 426 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 ... 2answers 298 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$... 0answers 97 views ### Reduction from a geometric decision problem to its maximization problem I am interested in the following NP-complete decision problem: ... 1answer 187 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 ... 1answer 416 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 NP^...
541 views

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 ...
340 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 ...
66 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 ...
381 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 ...
362 views

453 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 ...
171 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 oracle ...
359 views

427 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 ...
1k views

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