The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

An Isaac Newton Institute Programme

Logic and Algorithms

On lower bounds in non-classical logics

24th April 2006

Author: Pavel Pudlak (Czech Academy of Sciences)

Abstract

Whereas for classical logic it seems to be an extremely difficult problem, for some non-classical logics it is possible to prove exponential lower bounds on the lengths of proofs in (system based on axioms and derivation rules). For some modal logics recently such unconditional lower bounds have been proved. For intuitionistic logic we have only results based on unproven assumptions.