Seminar in Logic, Spring Semester 2000

NEW: Grades and projects, Status report.

Please reply by e-mail to janos@cs.technion.ac.il

Special meeting: Sunday, April 30, 16:30-18:30 in Taub 04

Seminar 23680x (CS) and Seminar 106940 (Mathematics)

Spring 2000: Prof. J.A. Makowsky

Complexity of Real and Algebraic Computation

Time: Wednesday 12:30-14:30
Place: taub 04

Version Winter 1998/99 , as Seminar 236805 (CS) and 106940 (Mathematics).

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 For additional reading, one may look into
  1. P. Buergisser, M. Clausen and A. Shokrollahi, Algebraic Complexity Theory, Springer 1996
  2. E. Engeler, Algorithmic Properties of Structures, World Scientific, 1993.
  3. B. Poizat, Les Petits Cailloux, Alea, 1995.
  4. C. Smorynski, Logic Number Theory I: An Introduction, Springer 1991
  5. J. Traub, G. Wasilkowski and H. Wozniakowski, Information Based Complexity, Aacademic Press, 1988.
  6. M. B. Pour-El and J.I. Richards, Computability in Analysis and Physics, Springer 1989
  7. 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).