<p>If a language <span class="math-container">$L_1$</span> in <span class="math-container">$\sf{NP}$</span> can be randomly reduced to a language <span class="math-container">$L_2$</span> in <span class="math-container">$\sf{NP}\cap \sf{coNP}$</span>, can we prove that <span class="math-container">$L_1$</span> is also in <span class="math-container">$\sf{NP}\cap \sf{coNP}$</span>?</p>
<p>More specifically, does
<span class="math-container">$\sf{GI}$</span> in <span class="math-container">$\sf{BPP^{L}}$</span>, for some <span class="math-container">$\sf{L\in NP\cap coNP}$</span> imply that <span class="math-container">$\sf{GI \in coNP}$</span>?</p>

CC BY-SA 4.0
2024-12-23T11:30:15.140Z
Maybe, depending on $L_1$; you can prove lots of things if you try. But if you actually wanted to ask whether *all* languages $L_1\in\mathsf{NP}$ that are randomly reducible to an $\mathsf{NP\cap coNP}$ language are in $\mathsf{NP\cap coNP}$, then this is not known. On the one hand, anything randomly reducible to $\mathsf{NP\cap coNP}$ is in $\mathsf{AM\cap coAM}$, which equals $\mathsf{NP\cap coNP}$ under plausible derandomization assumptions. On the other hand, any language in BPP is randomly reducible to a language in $\mathsf{P\subseteq NP\cap coNP}$, and $\mathsf{BPP\cap NP}$ is not ...
Emil Jeřábek
CC BY-SA 4.0
2024-12-23T11:36:53.847Z
... known to be included in coNP (e.g., there is an oracle relative to which $\mathsf{BPP=EXP^{NP}}$, see https://blog.computationalcomplexity.org/2005/08/extreme-oracles.html , which implies that $\mathsf{BPP\cap NP=NP\nsubseteq coNP}$, as PH cannot even collapse to $\Delta_2^P$ here due to the time hierarchy theorem).
Emil Jeřábek
CC BY-SA 4.0
2024-12-23T13:16:47.570Z
Thank you for your comments, Jeřábek. I have reorganized the question.
constantine
<reductions><randomized-algorithms><np>
Random reduction and NP $\cap$ coNP
constantine
# Random reduction and NP $\cap$ coNP

(Asked by: username_0 on 2024-12-23)

If a language $L\_1$ in $\sf{NP}$ can be randomly reduced to a language $L\_2$ in $\sf{NP}\cap \sf{coNP}$, can we prove that $L\_1$ is also in $\sf{NP}\cap \sf{coNP}$?

More specifically, does
$\sf{GI}$ in $\sf{BPP^{L}}$, for some $\sf{L\in NP\cap coNP}$ imply that $\sf{GI \in coNP}$?

**Tags:** reductions, randomized-algorithms, np
> **Comments:**
> **username_1**: Maybe, depending on $L_1$; you can prove lots of things if you try. But if you actually wanted to ask whether *all* languages $L_1\in\mathsf{NP}$ that are randomly reducible to an $\mathsf{NP\cap coNP}$ language are in $\mathsf{NP\cap coNP}$, then this is not known. On the one hand, anything randomly reducible to $\mathsf{NP\cap coNP}$ is in $\mathsf{AM\cap coAM}$, which equals $\mathsf{NP\cap coNP}$ under plausible derandomization assumptions. On the other hand, any language in BPP is randomly reducible to a language in $\mathsf{P\subseteq NP\cap coNP}$, and $\mathsf{BPP\cap NP}$ is not ...  
> **username_1**: ... known to be included in coNP (e.g., there is an oracle relative to which $\mathsf{BPP=EXP^{NP}}$, see https://blog.computationalcomplexity.org/2005/08/extreme-oracles.html , which implies that $\mathsf{BPP\cap NP=NP\nsubseteq coNP}$, as PH cannot even collapse to $\Delta_2^P$ here due to the time hierarchy theorem).  
> **username_0**: Thank you for your comments, Jeřábek. I have reorganized the question.  

---

## 0 answers

