¹A careful proof will have to take account of the fact that the lengths of the strings on which F and G have the same success probability (y for F and (y,r) for G) differ by a factor of 2, so the bound on F ’s success probability on strings of length n is the same as the bound on G’s success probability on strings of length m = 2n. One must show for all polynomials p(⋅) that the latter is bounded by for all sufficiently large even lengths m if the former is bounded by for all sufficiently large n.