Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Regular Talk:
The axiomatic derivation of absolute lower bounds

Edit abstract data

Speaker: Yiannis Moschovakis
Slot: Fri, 11:40-12:00, Amphitheater A (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 Valid HTML 4.01! Valid CSS!