<p>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 <a href="https://link.springer.com/chapter/10.1007/11672142_38" rel="nofollow noreferrer">showed</a> that $\mathbf{BPL} \subseteq \mathbf{L}/O(n)$ (see <a href="https://arxiv.org/abs/1711.00565" rel="nofollow noreferrer">this paper</a> for a refinement). It follows that $\mathbf{BPL}/O(n) = \mathbf{L}/O(n)$.</p>

CC BY-SA 3.0
2018-01-23T02:33:53.910Z
2018-01-23T02:33:53.910Z
William Hoza
<p>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)$.</p>

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

CC BY-SA 3.0
2015-10-27T18:01:28.843Z
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
CC BY-SA 3.0
2015-10-27T18:06:47.653Z
You're correct, I meant a class of functions instead of a specific function.
Ryan Dougherty
CC BY-SA 3.0
2015-10-27T18:10:51.083Z
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
CC BY-SA 3.0
2015-10-28T23:22:02.613Z
@Ricky, use repetition to reduce the error to be $<2^{-n}$. Argue that there is a sequence of random bits that doesn't work only for $<2^{-n}$ fraction of inputs (i.e. it works for all). Use Cook-Levin to turn it into a polynomial size circuit with extra inputs for random bits. Hardcode the sequence into the circuit. Since it is in BPP the number of random bits in the sequence is poly(n). So as soon as we have at least polynomial size advice the difference between BPP and P disappears. Does this answer your question or did I misunderstand what you are asking?
Kaveh
CC BY-SA 3.0
2015-10-28T23:35:31.897Z
@Ricky, I don't see why hard-coding would do that. (There are two ways to define advice classes: 1. define run-time w.r.t. only the input, 2. define run-time w.r.t. input+advice. The second one can access all advice bits if it has at least linear time.)
Kaveh
CC BY-SA 3.0
2015-10-28T23:45:31.400Z
@Ricky, yes, the class of $f$s should be closed under addition with polynomials for the argument to work (which is true for any class $O(f(n))$ where $poly(n)\ll f(n)$).
Kaveh
CC BY-SA 3.0
2018-01-23T16:37:12.053Z
The best we can currently show seems to be $BPP/f(n)\subseteq P/g(n)$ for $g(n)=O(n\cdot f(n))$: take a probabilistic circuit $C$  of size $s$ computing a boolean function $h$ (even with only **two-sided** error probability), apply Chernoff to show that the majority of $O(n)$ copies of $C$ (deterministic circuits of size $s$) computes $h$. This simple argument depends neither on the actual number of random bits, nor on their distribution, but increases the circuit size by the factor of $n$.
Stasys
CC BY-SA 3.0
2018-01-24T04:46:22.937Z
@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
CC BY-SA 3.0
2018-01-24T11:00:12.380Z
Well, complexity classes and Turing machines are not my strength ... P/poly for me stands for "poly-size circuits". And I used the inclusion in this sense.
Stasys
CC BY-SA 3.0
2018-01-24T17:06:00.513Z
@Stasys, I see, that's okay. $\mathbf{SIZE}(f(n))$ is the class of languages that can be computed by circuits of size $f(n)$, whereas $\mathbf{P}/f(n)$ is the class of languages that can be computed by polynomial-time Turing machines given $f(n)$ bits of advice. You're right that $\mathbf{SIZE}(\text{poly}) = \mathbf{P}/\text{poly}$. But for a specific polynomial, like e.g. $f(n) = n^2$, all we can say is that $\mathbf{SIZE}(n^2) \subseteq \mathbf{P}/O(n^2 \log n) \subseteq \mathbf{SIZE}(\text{poly})$.
William Hoza
CC BY-SA 3.0
2018-01-24T20:16:07.680Z
O.K., in your setting, when f(n) stands for the advice length, do we even know that $P/(t+n)\setminus P/t\neq \emptyset$? (Advice length increased by n bits.) In the "circuit language", we know this: circuits of size $s+n$ can do more than those of size $s$ (on inputs of length $n$). I mean: do we already understand the power of the "advice" well enough (when **everything** in polynomial time is allowed) to approach problems like BPP/f(n) vs. P/f(n)? Where also **randomness** comes to the game.
Stasys
CC BY-SA 3.0
2018-01-26T05:15:29.123Z
Hm, good question. I don't know.
William Hoza
<cc.complexity-theory><circuit-complexity><randomized-algorithms><derandomization><advice-and-nonuniformity>
Smallest $f(n)$ such that $P/f(n) = BPP/f(n)$?
Ryan Dougherty
# Smallest $f(n)$ such that $P/f(n) = BPP/f(n)$?

(Asked by: username_0 on 2015-10-27)

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?

**Tags:** cc.complexity-theory, circuit-complexity, randomized-algorithms, derandomization, advice-and-nonuniformity

> **Comments:**
> **username_1**: 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.  
> **username_0**: You're correct, I meant a class of functions instead of a specific function.  
> **username_1**: 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.  
> **username_1**: @Ricky, use repetition to reduce the error to be $<2^{-n}$. Argue that there is a sequence of random bits that doesn't work only for $<2^{-n}$ fraction of inputs (i.e. it works for all). Use Cook-Levin to turn it into a polynomial size circuit with extra inputs for random bits. Hardcode the sequence into the circuit. Since it is in BPP the number of random bits in the sequence is poly(n). So as soon as we have at least polynomial size advice the difference between BPP and P disappears. Does this answer your question or did I misunderstand what you are asking?  
> **username_1**: @Ricky, I don't see why hard-coding would do that. (There are two ways to define advice classes: 1. define run-time w.r.t. only the input, 2. define run-time w.r.t. input+advice. The second one can access all advice bits if it has at least linear time.)  
> **username_1**: @Ricky, yes, the class of $f$s should be closed under addition with polynomials for the argument to work (which is true for any class $O(f(n))$ where $poly(n)\ll f(n)$).  
> **username_2**: The best we can currently show seems to be $BPP/f(n)\subseteq P/g(n)$ for $g(n)=O(n\cdot f(n))$: take a probabilistic circuit $C$  of size $s$ computing a boolean function $h$ (even with only **two-sided** error probability), apply Chernoff to show that the majority of $O(n)$ copies of $C$ (deterministic circuits of size $s$) computes $h$. This simple argument depends neither on the actual number of random bits, nor on their distribution, but increases the circuit size by the factor of $n$.  
> **username_3**: @username_2, 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.  
> **username_2**: Well, complexity classes and Turing machines are not my strength ... P/poly for me stands for "poly-size circuits". And I used the inclusion in this sense.  
> **username_3**: @username_2, I see, that's okay. $\mathbf{SIZE}(f(n))$ is the class of languages that can be computed by circuits of size $f(n)$, whereas $\mathbf{P}/f(n)$ is the class of languages that can be computed by polynomial-time Turing machines given $f(n)$ bits of advice. You're right that $\mathbf{SIZE}(\text{poly}) = \mathbf{P}/\text{poly}$. But for a specific polynomial, like e.g. $f(n) = n^2$, all we can say is that $\mathbf{SIZE}(n^2) \subseteq \mathbf{P}/O(n^2 \log n) \subseteq \mathbf{SIZE}(\text{poly})$.  
> **username_2**: O.K., in your setting, when f(n) stands for the advice length, do we even know that $P/(t+n)\setminus P/t\neq \emptyset$? (Advice length increased by n bits.) In the "circuit language", we know this: circuits of size $s+n$ can do more than those of size $s$ (on inputs of length $n$). I mean: do we already understand the power of the "advice" well enough (when **everything** in polynomial time is allowed) to approach problems like BPP/f(n) vs. P/f(n)? Where also **randomness** comes to the game.  
> **username_3**: Hm, good question. I don't know.  

---

## 1 answers

### Answer by username_3 on 2018-01-23. Score: 3

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](https://link.springer.com/chapter/10.1007/11672142_38) that $\mathbf{BPL} \subseteq \mathbf{L}/O(n)$ (see [this paper](https://arxiv.org/abs/1711.00565) for a refinement). It follows that $\mathbf{BPL}/O(n) = \mathbf{L}/O(n)$.


---

