RequirementsIt will be assumed that students know the basics of calculability (especially primitive recursion) and complexity (P, NP).
Program requirementsexamen
TeacherArnaud Durand et Olivier Bournez
Weekly hours 4 h CM
Years

Syllabus

The objective of the course is to present several points of view on complexity from logic, recursion theory or analysis. The common feature of these approaches is that they move away from the notion of the machine (and its associated measures such as time and space) in favour of a more descriptive view of the calculation. The course aims in particular to study logical formalisms in terms of their power of expression and to present multiple characterizations of the usual complexity classes.

These descriptive or implicit approaches to complexity have had important applications in database theory, programming languages and more recently in the analysis of differential equation systems, or in understanding the power of alternative computational models based on bioinformatics, or analog computation.

We will first aim to present results on classical complexity [8, 13], to extend to algebraic models such as Blum Shub and Smale's model [3, 2], to continuous space such as neural network/deep learning models [17], then to time and continuous space such as Shannon's model [16].

Contents

  • Characterization of non-deterministic polynomial time by 2nd order logic (Fagin's theorem [10, 8]
  • Characterization of polynomial time by fixed point logic [8]
  • Characterization of complexity classes at Cobham [9, 15], Bellantoni and Cook [1]
  • Connections with circuits, non-uniform complexity [8]
  • Characterization of complexity classes in recursive analysis (complexity on the reals) [18, 7]
  • Extensions in Blum Shub and Smale models [12, 11]
  • Neural network/deep learning models [17]
  • Characterization of complexity classes using differential equations
    • discreet [5]
    • continuous [6, 14]
  • Links with some formal computational questions: D-finite functions and variants [4]

Bibliography

  • [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.