# Smallest $f(n)$ such that $P/f(n) = BPP/f(n)$?

It is well-known that $\mathsf{P/poly}(n) = \mathsf{BPP/poly}(n)$. It is a major open problem to prove the conjecture $\mathsf{P} = \mathsf{BPP}$. $\mathsf{P} = \mathsf{BPP}$ implies $\mathsf{P}/f(n) = \mathsf{BPP}/f(n)$ for all $f(n)$.

What is the smallest class of functions $f(n)$ such that $\mathsf{P}/f(n) = \mathsf{BPP}/f(n)$ is known?

• Is there a smallest? The usual argument uses $f(n)$ which is the number of random bits used by the algorithm which can an arbitrary polynomial. I.e. we know P/poly(n) = BPP/poly(n) but not for any fixed f(n) $\in$ poly(n) AFAIK. Since any function in $n^{\omega(1)}$ would work. – Kaveh Oct 27 '15 at 18:01
• You're correct, I meant a class of functions instead of a specific function. – Ryan Oct 27 '15 at 18:06
• We know any class containing polynomials suffices. Now to go lower means excluding some polynomial, i.e. is there an f(n) $\in$ poly(n) such that P/f(n) = BPP/f(n) holds. I don't think we have any such result. – Kaveh Oct 27 '15 at 18:10
• @Kaveh : $\:$ How do we know that $\big[\hspace{-0.02 in}$the class of functions that are eventually dominated by $2^{\hspace{.02 in}n}\hspace{-0.04 in}\big]$ suffices? $\hspace{.25 in}$ – user6973 Oct 28 '15 at 2:10
• @Stasys, I don't follow. If your argument were correct, wouldn't it prove that $\mathbf{P} = \mathbf{BPP}$ by taking $f(n) = 0$? It sounds like maybe you are thinking that every language in $\mathbf{BPP}/f(n)$ can be decided by probabilistic circuits of size $f(n)$, but that's not true. – William Hoza Jan 24 '18 at 4:46

Nothing better than $\mathbf{BPP}/\text{poly} = \mathbf{P}/\text{poly}$ is known. On the other hand, better results are known in the space bounded setting. Fortnow and Klivans showed that $\mathbf{BPL} \subseteq \mathbf{L}/O(n)$ (see this paper for a refinement). It follows that $\mathbf{BPL}/O(n) = \mathbf{L}/O(n)$.