Propositional proof complexity I.

- On p.70 I simplified the computation too much. One needs to estimate the total number of possible sets of critical pairs not by (2^k)^{k/2} but by more accurate

\sum_i {|h_i|}\choose{k_i} \le \sum_i k^{k_i} \le k^{k/2}

where k_i is the number of critical pairs in h_i,

and the total number of critical pairs by k rather than by k \cdot k/2 = k^2/2.

Then the exponent on the right hand side of the inequalities with a and b on p.71 (lines 7 and 12) is proportional to k rather than to k^2 and that is what is needed.

- P.71, line 4: term b should be n - n^\epsilon + k.

If you noticed some other errors/misprints/unclear parts, please let me know.

## I thank Mirek Olsak for pointing this out.

Acknowledgements