3
$\begingroup$

It is well known that $BPP \subset P/poly$, by probabilistic method.

Can this be strengthened: Is there a single string $a \in \{0,1\}^{\omega}$ such that there's a polynomial time deterministic Turing machine with $a$ written on separate tape that works on every input from $BPP$ in polynomial time? (This resembles König lemma a bit.)

  • 0
    Your accounts have been merged! :)2011-10-14

1 Answers 1

3

Suppose a language $L$ is accepted by a machine $M$ with polynomial advice $\alpha : n \mapsto \{ 0,1 \}^{\mathrm{poly}(n)}$. Then define $a \in \{0,1\}^{\omega}$ to be the infinite concatenation $\langle \alpha_0, \alpha_1, \alpha_2, \ldots, \alpha_n, \ldots \rangle$. This works as a single advice string for any input of arbitrary length.

Why? On an input of length $n$, we simply read the prefix of $a$ consisting of the first $n+1$ "blocks" $\langle \alpha_0, \alpha_1, \ldots, \alpha_n \rangle$, and then extract the string $\alpha_n$. This lets us simulate $M$ on the given input with advice $\alpha_n$, and we are done.

We also need to keep track of the length of the prefix we read. This is equal to $ |\alpha_0|+|\alpha_1|+\ldots+|\alpha_n| \leq (n+1) |\alpha_n| = O(n) \times \mathrm{poly}(n), $ which is, in turn, polynomially bounded. We are, of course, assuming (reasonably) that the length of the advice is a monotonically increasing function of the input length.

  • 0
    Thank you - so it is not limited to $BPP$. The question was created by an old account of mine, if they will be merged I'll mark as accepted.2011-10-10