# Non-uniform consequences of uniform derandomization

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.

• $C=D$ trivially implies $C/a(n)=D/a(n)$ for any classes $C$ and $D$ and any function $a(n)$. Nov 28, 2022 at 9:26
• 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)$. Nov 28, 2022 at 9:54
• @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. Nov 28, 2022 at 10:08
• 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'$. Nov 28, 2022 at 11:12
• Thanks again @EmilJeřábek, that clarifies things. If you write your comment as an answer I can accept it. Nov 28, 2022 at 12:05