<p>Adleman showed that <span class="math-container">$\mathsf{BPP/poly} \subseteq \mathsf{P/poly}$</span>.
Does <span class="math-container">$\mathsf{P} = \mathsf{BPP}$</span> have any implications for</p>
<ol>
<li><span class="math-container">$\mathsf{BPP}/a(n) \subseteq \mathsf{P}/a(n)$</span></li>
<li><span class="math-container">$\mathsf{BPTIME}(t(n))/a(n) \subseteq \mathsf{DTIME}(t'(n))/a'(n)$</span></li>
</ol>
<p>where <span class="math-container">$a(n)$</span> and <span class="math-container">$a'(n)$</span> are some fixed functions, e.g. <span class="math-container">$a(n) = \log_2(n)$</span> or even <span class="math-container">$a(n) = 1$</span>, and <span class="math-container">$t(n)$</span> and <span class="math-container">$t'(n)$</span> are some time-bound?</p>
<p>Note: If <span class="math-container">$a'(n) \geq t(n) + a(n)$</span>, then a deterministic TM <span class="math-container">$\mathcal{A}$</span> can include as advice the <span class="math-container">$a(n)$</span>-bit randomness of a randomized TM <span class="math-container">$\mathcal{R}$</span> plus <span class="math-container">$\mathcal{R}$</span>'s <span class="math-container">$t(n)$</span>-bit advice.</p>

CC BY-SA 4.0
2022-11-28T09:26:04.033Z
$C=D$ trivially implies $C/a(n)=D/a(n)$ for any classes $C$ and $D$ and any function $a(n)$.
Emil Jeřábek
CC BY-SA 4.0
2022-11-28T09:54:59.967Z
Oh, and I forgot to mention that P = BPP implies $\mathrm{BPTIME}(t(n))\subseteq\mathrm{DTIME}(t(n)^{O(1)})$ for any time-constructible function $t(n)\ge n$ by the obvious padding argument. Thus also $\mathrm{BPTIME}(t(n))/a(n)\subseteq\mathrm{DTIME}(t(n)^{O(1)})/a(n)$.
Emil Jeřábek
CC BY-SA 4.0
2022-11-28T10:08:26.377Z
@EmilJeřábek Thanks for the response. $\mathsf{P}/a(n)$ is the class of languages that are decidable by poly-time deterministic TMs with advice of length $a(n)$.
What would be the analog definition of $C/a(n)$ for general $C$?
Maybe this is obvious but I don't see it atm.
Nicholas Brandt
CC BY-SA 4.0
2022-11-28T11:12:03.460Z
The class of languages $L$ such that there exists $L'\in C$ and a sequence of advice strings $\{w_n:n\in\mathbb N\}$, $|w_n|\le a(n)$, such that $x\in L\iff(x,w_{|x|})\in L'$.
Emil Jeřábek
CC BY-SA 4.0
2022-11-28T12:05:30.420Z
Thanks again @EmilJeřábek, that clarifies things. If you write your comment as an answer I can accept it.
Nicholas Brandt
<cc.complexity-theory><derandomization>
Non-uniform consequences of uniform derandomization
Nicholas Brandt
# Non-uniform consequences of uniform derandomization

(Asked by: username_0 on 2022-11-28)

Adleman showed that $\mathsf{BPP/poly} \subseteq \mathsf{P/poly}$.
Does $\mathsf{P} = \mathsf{BPP}$ have any implications for

1. $\mathsf{BPP}/a(n) \subseteq \mathsf{P}/a(n)$
2. $\mathsf{BPTIME}(t(n))/a(n) \subseteq \mathsf{DTIME}(t'(n))/a'(n)$

where $a(n)$ and $a'(n)$ are some fixed functions, e.g. $a(n) = \log\_2(n)$ or even $a(n) = 1$, and $t(n)$ and $t'(n)$ are some time-bound?

Note: If $a'(n) \geq t(n) + a(n)$, then a deterministic TM $\mathcal{A}$ can include as advice the $a(n)$-bit randomness of a randomized TM $\mathcal{R}$ plus $\mathcal{R}$'s $t(n)$-bit advice.

**Tags:** cc.complexity-theory, derandomization
> **Comments:**
> **username_1**: $C=D$ trivially implies $C/a(n)=D/a(n)$ for any classes $C$ and $D$ and any function $a(n)$.  
> **username_1**: Oh, and I forgot to mention that P = BPP implies $\mathrm{BPTIME}(t(n))\subseteq\mathrm{DTIME}(t(n)^{O(1)})$ for any time-constructible function $t(n)\ge n$ by the obvious padding argument. Thus also $\mathrm{BPTIME}(t(n))/a(n)\subseteq\mathrm{DTIME}(t(n)^{O(1)})/a(n)$.  
> **username_0**: @EmilJeřábek Thanks for the response. $\mathsf{P}/a(n)$ is the class of languages that are decidable by poly-time deterministic TMs with advice of length $a(n)$. What would be the analog definition of $C/a(n)$ for general $C$? Maybe this is obvious but I don't see it atm.  
> **username_1**: The class of languages $L$ such that there exists $L'\in C$ and a sequence of advice strings $\{w_n:n\in\mathbb N\}$, $|w_n|\le a(n)$, such that $x\in L\iff(x,w_{|x|})\in L'$.  
> **username_0**: Thanks again @EmilJeřábek, that clarifies things. If you write your comment as an answer I can accept it.  

---

## 0 answers

