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


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