Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Cours 2.33.3

2.33.3 Computing over the reals: models, computability, complexity (24h, 3ECTS)

Responsable: Olivier Bournez, Professeur Ecole polytechnique.

Thursday, from 12h45 to 15h45.

Room 1004.

Motivations et objectifs du cours

This course is discussing computability and complexity theory for computations over the real numbers.

Pre-requisites

Basic notions from theoretical computer science (Turing machines, NP-completeness, P, NP, etc...)

Course Description

We will introduce various way to model and discuss computations over the real numbers:

For example:

* Computable analysis: a real is seen as a sequence of converging rational numbers, and one considers Turing machines transforming rational sequences into rational sequences

* Continuous time models of computation: what can be computed using analog electronics, circuits?

Course Language

English upon request. French by default.

Messages :

Messages: * The first lecture is on Thursday 16th September 2021

* No lecture on November 4th 2021

* Exam on November 25th 2021, 12h45.

VERSION 2021

The course will be done on blackboard.

Some course notes will be available and put online at the end of each course.

* Lecture 1:

* Lecture 2:

  • Computable analysis: computable functions (see consolidated pdf below)
  • Course notes: Chapter 4 and 5 of pdf below.

* Lecture 3:

  • Computable analysis: representing spaces of functions, subsets. Intermediate value theorem (see consolidated pdf below)
  • Course notes: Chapter 6 and 7, 8 of pdf below.

* Lecture 4:

  • Computable analysis: Intermediate value theorem. Complexity. Some selected results
  • Course notes: Chapter 8, 9 and 10 of pdf below.

part I

Bibliography for 4 first courses:

* Klaus Weihrauch. Computable Analysis: an introduction. Springer. 2000.

* http://cca-net.de/vasco/, an the excellent “Tutorial: Computability & Complexity in Analysis” on this web page.

* Vasco Brattka, Peter Hertling, and Klaus Weihrauch. A tutorial on computable analysis. In S. Barry Cooper, Benedikt Löwe, and Andrea Sorbi, editors, New Computational Paradigms: Changing Conceptions of What is Computable, pages 425-491. Springer, New York, 2008.

* Lecture 5:

  • Static indecidability. Example of Richardson Theorem
  • Dynamic undecidability. Computing with PCD and PAM

* Lecture 6:

  • The General Purpose Analog Computer (GPAC)
  • GPAC-generable functions and closure properties
  • Simulating a Turing Machine with GPAC-generable functions in discrete time

* Lecture 7:

  • Simulating a Turing Machine with GPAC-generable functions in continuous time.

Notes: part II (updated)

  • Complexity and GPAC: polynomial time corresponds to length, up to polynomial time.

Polynomial Time Corresponds to Solutions of Polynomial Ordinary Differential Equations of Polynomial Length

  • Computing over a structure: the basic model, circuits, and definition of complexity classes based on circuits. (see notes below)

* Lecture 8:

  • Computing over a structure: P, NP, NP-completeness, relations with discrete complexity. See notes below + articles of Koiran below.

+ Bibliography:

- Blum, L., BLUM, L. A., Cucker, F., Shub, M., & Smale, S. (1998). Complexity and real computation. Springer Science & Business Media.
- Poizat, B. (1995). Les petits cailloux (Vol. 995). Lyon: Aléas.
- Koiran, P. (1994). Computing over the reals with addition and order. Theoretical Computer Science, 133(1), 35-47.
- Koiran, P. (1997). A weak version of the Blum, Shub, and Smale model. Journal of Computer and System Sciences, 54(1), 177-189.

part III

BELOW IS THE PAGE OF 2018

Course content in 2018 (2021 will be different) :

The course will be done on blackboard.

Some course notes will be available and put online at the end of each course.

* Lecture 1:

  • Computable analysis: computable reals. (see consolidated pdf below)

* Lecture 2:

  • Computable analysis: computable functions (see consolidated pdf below)

* Lecture 3:

  • Computable functions: oracle view. Modulus of continuity.
  • Computable subsets.

* Lecture 4:

  • Intermediate Value Theorem
  • Complexity

* Lecture 5:

  • Selected results
  • Complexity

* Lecture 6:

* Lecture 7:

  • Computing with dynamical systems with non-necessarily rationals coefficients
  • Space/time contractions for PCD Systems

* Lecture 8:

Course notes :

Course notes:

See course above.

Bibliography (Edition 2018-2019) :

Bibliography for first courses:

* Klaus Weihrauch. Computable Analysis: an introduction. Springer. 2000.

* http://cca-net.de/vasco/, et l'excellent “Tutorial: Computability & Complexity in Analysis” sur cette page.

* Vasco Brattka, Peter Hertling, and Klaus Weihrauch. A tutorial on computable analysis. In S. Barry Cooper, Benedikt Löwe, and Andrea Sorbi, editors, New Computational Paradigms: Changing Conceptions of What is Computable, pages 425-491. Springer, New York, 2008.

Relevant Courses (version 2018)

 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA