Computability in Europe 2006
Logical Approaches to Computational Barriers


Regular Talk:
The axiomatic derivation of absolute lower bounds


Speaker: Yiannis Moschovakis
Slot: Array, 11:40-12:00, col. 1

Abstract

I will outline a method for deriving lower bounds for the complexity
of problems (especially in arithmetic) which are absolute
(universal), i.e., they apply to all algorithms; the key idea is to
derive lower bounds from three axioms for algorithms, which are
natural and easily shown to apply to all known models of computation.

websites: Arnold Beckmann 2008-05-19