The Complexity of Pure and Impure Proof

Abstract: It has often been claimed that pure proofs are less valuable than impure proofs because of the relative “difficulty” or “complexity” of pure versus impure proofs. Whatever advantages pure proof may have over impure proof would be countered by disadvantages if impure proof is systematically “easier” or “simpler” than pure proof. In order to evaluate this claim, it is helpful to identify precise measures of proof complexity for which the claim may be tested. In this talk we single out a “topological” measure of proof complexity studied in recent work by Alessandra Carbone, and evaluate the thesis for that measure.