1
$\begingroup$

I have written the following answer as an attempt to prove a variation of Sispser-Lautmann theorem, but it was rejected without any comments. I would appreciate if anyone can find the flaws in this attempt of proof. The variation is the following: given a language $A$ in $BPP$ that has a probabilistic turing machine running in polynomial time $t(n)$, with an error at most $\frac{1}{10t(n)}$, prove that $A \in \Sigma_2^p$.

My outline for the proof was the following:

  • From the amplification lemma of $BPP$ (meanning running poly-many times, choosing majority, and using chernoff's bound to bound the error), we can without loss of generality assume there is a probabilistic machine $M$ for $A$ that run in polynomial time $q(n)$ and with error at most $2^{-p(n)}$
  • When fixing the coins that $M$ uses, $M$ is deterministic, and there is a SAT formula that is satisfied if only if M accepts for the same coins and input.
  • There is a $\Sigma_2$-sat formula that is equivalent to $M$: there exist $p(n)$ coins that for any other sequence of coins $M$ accepts.

Thanks

$\endgroup$
  • 1
    $\begingroup$ (1) You cannot get error at most $2^{-p(n)}$ and running time $p(n)$. The running time will be a larger polynomial $q(n)$. (2) The number of incorrect coin sequences is much, much larger than $p(n)$. It is exponential in $n$. If you throw a coin at every step, it’s just bounded by $2^{q(n)-p(n)}$. In other words, the number of bad coin sequences may be exponential even for the original algorithm, and amplification by running many independent instances can only increase this number (even though it decreases its ratio to good coin sequences). $\endgroup$ – Emil Jeřábek May 17 '18 at 9:31
  • $\begingroup$ Thanks for your answer. I edited to address (1), it was just notational error, I am sorry. Could you please elaborate on (2)? The coin sequences for M represent all of the coins it uses to run the original algorithm many times independently, so if the ratio is reduced, isn't it enough? $\endgroup$ – s3683168 May 17 '18 at 9:41
  • $\begingroup$ I understood my mistake, thank you! $\endgroup$ – s3683168 May 17 '18 at 10:04

Your Answer

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

Browse other questions tagged or ask your own question.