Invited talk: On Dierences in Proofs Between Intuitionistic and Classical Logic Aleksy Schubert 0 Institute of Informatics, University of Warsaw ul. S. Banacha 2 , 02097 Warsaw , Poland

The presentation will contrast the complexity results for proving assertions in classical and intuitionistic logic. The comparison will be built upon the known results for propositional logic and predicate one. The predicate case will be based upon the Mints hierarchy in intuitionistic logic which will be contrasted with its counterpart i.e. the prenex hierarchy in classical logic. The dierences in complexity will be illustrated with examples of particular proving mechanisms that are responsible for the divergence, which should facilitate the understanding of where the mathematics is done constructively.