This paper is concerned with the complexity of proofs and of searching for proofs in two propositional proof systems: Resolution and Polynomial Calculus (PC). For the former system we show that the recently proposed algorithm of BenSasson and Wigderson (STOC 99) for searching for proofs cannot give better than weakly exponential performance. This is a consequence of showing optimality of their general relationship referred to as size-width tradeoff. We moreover obtain the optimality of the size-width tradeoff for the widely used restrictions of resolution: regular, Davis-Putnam, negative, positive and linear.As for the second system, we show that the direct translation to polynomials of a CNF formula having short resolution proofs, cannot be refuted in PC with degree less than \math. A consequence of this is that the simulation of resolution by PC of Clegg, Edmonds and Impagliazzo (STOC 92) cannot be improved to better than quasipolynomial in the case we start with small resolution proofs. We conjecture that the simulation of Clegg at al. is optimal.