On the Computational Complexity of Cut-Reduction
Klaus Aehlig, Arnold Beckmann · Proceedings - Symposium on Logic in Computer Science · 2008
Using appropriate notation systems for proofs, cut-reduction can often be rendered feasible on these notations. Explicit bounds can be given. Developing a suitable notation system for Bounded Arithmetic, and applying these bounds, all the known results on definable functions of certain such theories can be reobtained in a uniform way.