PrérequisOn fera l’hypothèse que les étudiants connaissent les bases de la calculabilité (récursion primitive notamment) et de la complexité (P, NP).
Validationexamen
EnseignantOlivier Bournez et Arnaud Durand
Horaires hebdomadaires 4.0 h CM
Années

Syllabus

L’objectif du cours est de présenter plusieurs point de vue sur la complexité venant de la logique, de la théorie de la récursion ou de l’analyse. Ces approches ont pour point commun de s’abstraire de la notion de machine (et de ses mesures associées comme le temps et l’espace) au profit d’une vision plus descriptive du calcul. Le cours vise notamment à étudier des formalismes logiques sous l’angle de leur pouvoir d’expression et à présenter de multiples caractérisations des classes de complexité usuelles.

Ces approches de le complexité dîtes descriptives ou implicites ont connu des applications importantes en théorie des bases de données, des langages de programmation ainsi que plus récemment autour de l’analyse des systèmes d’équations différentielles, ou autour de la compréhension de la puissance de modèles alternatifs de calculs basés sur la bioinformatique, ou le calcul analogique.

On visera à présenter dans un premier temps des résultats sur la complexité classique [8, 13], pour aller vers des extensions à des modèles algébriques comme le modèle de Blum Shub et Smale [3, 2], à espace continus comme les modèles de réseaux de neurones/deep learning [17], puis à temps et espace continu comme le modèle de Shannon [16].

Sommaire

  • Caractérisation du temps non-déterministe polynomial par la logique du 2ième ordre (théorème de Fagin [10, 8]
  • Caractérisation du temps polynomial par les logiques de points fixes [8]
  • Caractérisation de classes de complexité à la Cobham [9, 15], à la Bellan- toni et Cook [1]
  • Liens avec les circuits, complexité non-uniforme [8]
  • Caractérisation de classes de complexité en analyse récursive (complexité sur les réels) [18, 7]
  • Extensions dans les modèles à la Blum Shub et Smale [12, 11]
  • Modèles de réseaux de neurones/deep learning [17]
  • Caractérisation de classes de complexité à l’aide d’équations différentielles
    • discrètes [5]
    • continues [6, 14]
  • Liens avec certaines questions du calcul formel: fonctions D-finies et variantes [4]

Bibliographie

  • [1] S. Bellantoni and S. Cook. A new recursion-theoretic characterization of the poly-time functions. Computational Complexity, 2(2):97–110, 1992.
  • [2] L. Blum, F. Cucker, M. Shub, and S. Smale. Complexity and Real Compu- tation. Springer, 1998.
  • [3] L. Blum, M. Shub, and S. Smale. On a theory of computation and complex- ity over the real numbers; NP completeness, recursive functions and univer- sal machines. Bulletin of the American Mathematical Society, 21(1):1–46, July 1989.
  • [4] Alin Bostan, Frédéric Chyzak, Marc Giusti, Romain Lebreton, Grégoire Lecerf, Bruno Salvy, and Éric Schost. Algorithmes efficaces en calcul formel. published by the Authors, 2017.
  • [5] O. Bournez, A. Durand, and S. Ouazzani. Recursion schemes, discrete differential equations and characterization of polynomial time computation. Technical report, October 2018.
  • [6] O. Bournez, D. S. Graça, and A. Pouly. Polynomial Time corresponds to Solutions of Polynomial Ordinary Differential Equations of Polynomial Length. Journal of the ACM, 64(6):38:1–38:76, 2017.
  • [7] Vasco Brattka. Recursive characterization of computable real-valued func- tions and relations. Theoretical Computer Science, 162(1):45–77, 1996.
  • [8] Peter Clote and Evangelos Kranakis. Boolean functions and computation models. Springer Science & Business Media, 2013.
  • [9] A. Cobham. The intrinsic computational difficulty of functions. In Y. Bar-Hillel, editor, Proceedings of the International Conference on Logic, Methodology, and Philosophy of Science, pages 24–30. North-Holland, Am- sterdam, 1962.
  • [10] R. Fagin. Generalized first-order spectra and polynomial-time recognizable sets. In R. M. Karp, editor, Complexity in Computer Computations, pages 43–73. American Mathematics Society, Providence R.I., 1974.
  • [11] Erich Grädel and Y. Gurevich. Tailoring recursion for complexity. Journal of Symbolic Logic, 60(3):952–969, Sept. 1995.
  • [12] Erich Grädel and Yuri Gurevich. Metafinite model theory. Information and Computation, 140(1):26–81, 10 January 1998.
  • [13] L. Libkin. Elements of finite model theory. EATCS Series. Springer, 2004.
  • [14] Amaury Pouly. Continuous models of computation: from computability to complexity. PhD thesis, Ecole Polytechnique and Unidersidade Do Algarve, Defended on July 6, 2015. 2015. https://pastel.archives-ouvertes.fr/tel-01223284, Prix de Thèse de l’Ecole Polyechnique 2016, Ackermann Award 2017.
  • [15] H. E. Rose. Subrecursion, Functions and Hierarchies. Clarendon Press, Oxford, 1984.
  • [16] C. E. Shannon. Mathematical theory of the differential analyser. Journal of Mathematics and Physics MIT, 20:337–354, 1941.
  • [17] Hava T. Siegelmann. Neural Networks and Analog Computation - Beyond the Turing Limit. Birkauser, 1999.
  • [18] K. Weihrauch. Computable Analysis: an Introduction. Springer, 2000.