Talk:Sipser–Lautemann theorem

lemma 1 looks strange

In Lemma 1 you need

$\sum _{r}{\frac {1}{2^{|x|\cdot |r|}}}={\frac {1}{2^{|x|}}}$

for which there are $2^{r}$ summands. Though, this equality is just plain wrong, as it is equivalent to

$2^{|r|}{\frac {1}{2^{|x|\cdot |r|}}}={\frac {1}{2^{|x|}}}$

$2^{|r|}\cdot 2^{|x|}=2^{|x|\cdot |r|}$

$2^{|r|+|x|}=2^{|x|\cdot |r|}$

$|r|+|x|=|x|\cdot |r|$ —Preceding unsigned comment added by 141.24.51.251 (talk) 13:44, 23 March 2011 (UTC)

I think both proofs are the same

The page gives two proofs for the theorem and claims the first is based on Sipser(-Gacs) and the second on Lautemann but (imo) both proofs are the same (based on Lautemann), Sipser used hash functions.

Ps. I really don't think it's correct to call it Sipser-Lautemann theorem as the first person to prove the result was Gacs, see e.g. Trevision calls it Gács-Sipser-Lautemann: http://lucatrevisan.wordpress.com/2010/04/27/cs254-lecture-5-the-polynomial-hierarchy/ — Preceding unsigned comment added by 80.98.160.141 (talk) 05:23, 2 February 2014 (UTC)