Apr 10, Beklemishev & Rastsvetaev: Query Complexity and Formal
Wolfgang Slany
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.
#####################################################################
Informationsdienst Inst. f. Informationssysteme, Abt. f. Datenbanken
und Artificial Intelligence TU Wien E184/2. Fuer regelmaessige Zusendung
dieser Nachrichten senden Sie email an list...@dbai.tuwien.ac.at,
mit "SUB PUBLIC <Ihr Name>" als einziger Zeile (kein Subject).
Siehe auch http://www.dbai.tuwien.ac.at/marchives/public/