Complexities of Proof-Theoretical Reductions