Responsable: Olivier Bournez, Professeur Ecole polytechnique.

Thursday, from 12h45 to 15h45.

Room 1004.

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

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

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?

English upon request. French by default.

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

* No lecture on November 4th 2021

* Exam on November 25th 2021, 12h45.

The course will be done on blackboard.

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

* Lecture 1:

• Introduction, motivation du cours
• Computable analysis: computable reals. (see consolidated pdf below)
• Course notes: Chapter 3 of pdf below.

* 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

The course will be done on blackboard.

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

* Lecture 1:

• Introduction
• 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:

• Complexity (end)
  • Consolidated pdf: courses 1-6 |Computable analysis

* Lecture 7:

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

• Dynamic undecidability

• The General Purpose Analog Computer / Differential Analysers

* Lecture 8:

• * The General Purpose Analog Computer: Stability Properties of generable functions
• The General Purpose Analog Computer: Computability Properties
• (cf Dynamic undecidability also for computability properties)

Course notes:

See course above.

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.

The following is a coherent list of courses on the thematic 'Algorithms and Complexity'.

* 2-11-1 Advanced Algorithms * 2-11-2 Randomness in Complexity * 2-12-1 Techniques in Cryptography and Cryptanalysis * 2-13-2 Error correcting codes and applications to cryptography * 2-18-1 Distributed algorithms for the networks * 2-18-2 Algorithmique distribuée avec mémoire partagée * 2-24-1 Optimisation * 2-29-1 Graph algorithms * 2-33-1 Theory of Computations * 2-34-1 Quantum information and applications * 2-38-1 Algorithms for embedded graphs