5
$\begingroup$

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?

$\endgroup$
17
  • $\begingroup$ 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. $\endgroup$
    – Kaveh
    Commented Oct 27, 2015 at 18:01
  • $\begingroup$ You're correct, I meant a class of functions instead of a specific function. $\endgroup$ Commented Oct 27, 2015 at 18:06
  • $\begingroup$ 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. $\endgroup$
    – Kaveh
    Commented Oct 27, 2015 at 18:10
  • $\begingroup$ @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}$ $\endgroup$
    – user6973
    Commented Oct 28, 2015 at 2:10
  • 1
    $\begingroup$ @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. $\endgroup$ Commented Jan 24, 2018 at 4:46

1 Answer 1

3
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.