Apr 10, Beklemishev & Rastsvetaev: Query Complexity and Formal Arithmetic


Subject: Apr 10, Beklemishev & Rastsvetaev: Query Complexity and Formal Arithmetic
From: Wolfgang Slany (wsi@dbai.tuwien.ac.at)
Date: Thu Apr 06 2000 - 14:48:10 MET DST


            KURT GÖDEL SOCIETY

            LECTURE ANNOUNCEMENT

We are pleased to inform you that Prof. L. Beklemishev and
Prof. A. Rastsvetaev will give a lecture:

SPEAKER: Prof. L. Beklemishev and Prof. A. Rastsvetaev
                Institute for Algebra and Computational Mathematics
                University of Technology, Vienna

TITLE: QUERY COMPLEXITY AND FORMAL ARITHMETIC

DATE & TIME: Monday, April 10, 2000
                16.45

LOCATION: Seminarraum des Instituts für Computersprachen (Prof. Leitsch)
                Favoritenstrasse 9
                Stiege 1
                3. Stock

ABSTRACT:
In the theory of strong fragments of Peano
arithmetic it is the query complexity measure
(the number of necessary oracle queries), rather
than the more usual time or space measures, that
plays a role. In the first part of the talk these
relationships will be discussed and the example
of induction schema for decidable predicates will
be treated.

In the second part of the talk the query
complexity of the problem of finding a local
maximum point of a function on a bounded interval
will be sharply estimated. The optimal algorithm
for this problem happens to be related to the famous
Fibonacci numbers. The query complexity is then
estimated by log_c(n)+O(1), where c is the "golden
ratio" constant.



This archive was generated by hypermail 2b25 : Thu Apr 06 2000 - 16:19:21 MET DST