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?

Improve this question
$\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
    Oct 27 '15 at 18:01
  • $\begingroup$ You're correct, I meant a class of functions instead of a specific function. $\endgroup$
    – Ryan
    Oct 27 '15 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
    Oct 27 '15 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
    Oct 28 '15 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$
    – William Hoza
    Jan 24 '18 at 4:46
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)$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.