All Questions
Tagged with separation oracles
3 questions
3
votes
0
answers
482
views
Oracle separating $coNP$ and $NP/poly$
I'd like to prove that, with respect to some adversarial oracle $O$, $coNP^O \not\subseteq NP/poly^O$. I was thinking of using $\textsf{UNSAT}$ for this and to build my oracle as follows: $O$ will "...
- 137
8
votes
0
answers
153
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. ...
- 81
12
votes
1
answer
491
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}^{\...
- 16.6k