Computability in Europe 2008
Logic and Theory of Algorithms
|Slot:||Fri, 11:40-12:00, Amphitheater A (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|