Table of Contents
## Cours 2.33## 2.33 Complexity over the RealsResponsable: Olivier Bournez, Professeur Ecole polytechnique, bournez@lix.polytechnique.fr, https://www.lix.polytechnique.fr/Labo/Olivier.Bournez Thursday, from 8:45>11:45 Room 1004. ## Motivation and course objectivesThis course discusses computation (computability and complexity) theory for computations over real numbers. This is a classical complexity and computability course but applied to questions about real numbers or functions over the numbers. It covers also models based on circuits, or algebraic models. ## Pre-requisitesBasic notions from theoretical computer science (Turing machines, NP-completeness, P, NP, etc...) ## Course DescriptionWe will introduce various ways to model and study complexity of algorithms 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 * Complexity of models from deep learning: deep learning (a.k.a neural network) models are particular models of computation dealing with real numbers. How can we measure the associated complexity? * Continuous time models of computation: what can be computed using analog electronics, or circuits? ## Course LanguageEnglish upon request ⇒ So ENGLISH for 2024. ## Evaluation 2024**a homework assignment serving as midterm exam**: HOMEWORK AVAILABLE HERE- a final written exam:
**ON THURSDAY 28th 2024 (MORNING, USUAL TIME OF THE LECTURE)**
## Messages :Messages: * The course stats on Thursday September 19th 2024 * No lecture on October 3 ## 2024 EDITIONDetails to come. But we will cover above mentioned topics, namely: * Computable analysis * Complexity of models from deep learning * Continuous time models of computation ## VERSION 2024The 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, tentative of a demo on a THAT.
- Computable analysis: computable reals, Type 2 Turing Machine, notation, representation, computable function
- computable implies continuous
* Lecture 2: - Intermediate value theorem: various computable/uncomputable statements.
- Computability vs Continuity.
* No lecture on Thursday October 3rd !! * Lecture 3: - Computability vs Continuity (continued).
- Alternative characterizations of computable functions.
- Statement of some selected results from computability.
- Myhill's theorem and its proof.
* Lecture 4: - Complexity in computable analysis: the approach of Ker I Ko's book.
- Selected results
* Lecture 5: - Complexity of operators in computable analysis: some basic problems
- Complexity of operators in computable analysis: the approach of Kawamura & Cook
* Lecture 6: - Complexity of operators in computable analysis: some examples of applications
Here are the lecture notes for the computable analysis part: up to this point. Related lecture notes (updated, relative to Lecture 1 to Lecture 6) - Computing over an arbitrary structure. The BSS model.
## HISTORICAL PAGES / ARCHIVES## BELOW IS THE PAGE OF 2021
## 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.
part I (not available any more) 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 (not available any more)
* 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 |