Seminar in Logic 1998/99
Seminar 236805 (CS) and 106940 (Mathematics),
Winter 1998/9: Prof. J.A. Makowsky
Complexity of Real and Algebraic Computation
Time: Thursday 10:30-12:30
Ulman 503 (starting December 31.98)
We have been moved again, sorry.
The locations (Amado 814, Fishbach 413) are not valid anymore.
Short description
Classical computability and Complexity Theory
deals with computations on strings (Turing) or on the natural numbers
(Skolem, Goedel). These two approaches are easily seen to
be intertranslatable. On the other hand the set of properties of the
natural numbers expressible in First Order Logic is undecidable , i.e.
not computable (Goedel).
This stands in contrast to the real numbers,
where the set of First Order properties is decidable (Tarski),
but where several theories of complexity have been developed.
In the seminar we sketch the basics of complexity theory over the reals
(and related algebraic structures).
We discuss several models of computation, their associated notions
of reductions and their inherently difficult problems.
This is an active subject of research with various
topics for M.Sc. and Ph.D. theses.
Related courses are Definability and Computability
(236331) and Algebraic Complexity(236311).
Literature
Most of the seminar will follow closely
-
[BCSS]
L. Blum, F. Cucker, M. Shub and S. Smale,
Complexity and Real Computation, Springer 1997
For additional reading, one may look into
-
P. Buergisser, M. Clausen and A. Shokrollahi,
Algebraic Complexity Theory, Springer 1996
-
E. Engeler, Algorithmic Properties of Structures, World Scientific, 1993.
-
B. Poizat, Les Petits Cailloux, Alea, 1995.
-
C. Smorynski, Logic Number Theory I: An Introduction,
Springer 1991
-
J. Traub, G. Wasilkowski and H. Wozniakowski,
Information Based Complexity, Aacademic Press, 1988.
-
M. B. Pour-El and J.I. Richards,
Computability in Analysis and Physics, Springer 1989
-
ps-files or references of
Articles from Journals or Books
Further pointers
relevant to this topic.
Prerequisites and Requirements
Students should feel a bit familiar with basic mathematics
(Algebra and Numeric Analysis), with Computability (236343) and a bit with
Logic 1 (234292).
-
Two hour presentations of material from [BCSS],
in groups of up to three students.
Projects and Talks
-
Preparation of lecture notes based on seminar presentations
(in groups of maximally two students).