Table of Contents
## 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 coursThis course is discussing computability and complexity theory for computations over the real numbers. ## Pre-requisitesBasic notions from theoretical computer science (Turing machines, NP-completeness, P, NP, etc...) ## Course DescriptionWe 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 LanguageEnglish 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 2021The 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)
- 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.
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.
- 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. ## 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: - 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
* Lecture 8: - (cf Dynamic undecidability also for computability properties)
## 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)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 |