<p>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$.</p>

<p>My outline for the proof was the following:</p>

<ul>
<li>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)}$ </li>
<li>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.</li>
<li>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.</li>
</ul>

<p>Thanks</p>

CC BY-SA 4.0
2018-05-17T09:31:49.957Z
(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).
Emil Jeřábek
CC BY-SA 4.0
2018-05-17T09:41:34.870Z
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?
s3683168
<cc.complexity-theory><complexity-classes><randomness><proofs><polynomial-hierarchy>
Proof of Sipser-Lautmann Theorem
s3683168
# Proof of Sipser-Lautmann Theorem

(Asked by: username_0 on 2018-05-17)

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

**Tags:** cc.complexity-theory, complexity-classes, randomness, proofs, polynomial-hierarchy
> **Comments:**
> **username_1**: (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).  
> **username_0**: 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?  

---

## 0 answers

