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

Cours 2.33

2.33 Complexity over the Reals

Responsable: 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 objectives

This 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-requisites

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

Course Description

We 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 Language

English 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 EDITION

Details to come.

But we will cover above mentioned topics, namely:

* Computable analysis

* Complexity of models from deep learning

* Continuous time models of computation

VERSION 2024

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, 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.

Related lecture notes




HISTORICAL PAGES / ARCHIVES




BELOW IS THE PAGE OF 2021

Warning: the 2024 edition will be different, and will focus on rather different subjects.

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 (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.

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