Calculabilité dans les structures algébriques dénombrables

Henri Lombardi
Première partie de ma thèse, réimprimée (avec de très légères améliorations) aux Publications Mathématiques de Besançon. 1990

Résumé :

Cette étude est consacrée aux ensembles discrets énumérables lorsqu'on adopte le point de vue des constructions d'une classe donnée C. La classe que nous avons essentiellement en vue est celle des constructions en temps polynomial. La démarche générale que nous suivons est de relativiser à une classe de construction donnée les méthodes de mathématiques constructives.
Dans la section A, nous donnons les définitions de base, et quelques résultats élémentaires.
Dans la section B, nous nous intéressons aux structures algébriques dénombrables effectives.
Les notions de "calcul algébrique", "calcul algébrique formel" et "calcul de classe C" interfèrent alors entre elles. Cela nous amène à la notion de "structure algébrique complètement C-calculable", qui s'avère être une bonne notion.
Par définition, une présentation d'une structure algébrique est complètement C-calculable lorsque l'évaluation des formules est C-calculable.
Nous établissons donc un lien entre la notion introduite et les présentations "par formule" ou "en magma" (section e).
Nous montrons que les structures algébriques les plus élémentaires sont complètement P-calculables, et en général "de manière naturelle".
Cela implique qu'il y a une P-présentation naturellement attachée à une structure algébrique élémentaire.
Par exemple la P-présentation naturelle de ( N, 0, 1, + ) est la présentation en unaire, tandis que la présentation naturelle de ( N, 0, 1, +, x ) est la présentation en binaire.
De nombreuses structures algébriques "libres de type fini" sont complètement P-calculables et ont une structure de P-calculabilité naturelle. Par exemple les algèbres de polynômes (à un nombre fini d'indéterminées) sur Z, Q ou sur un anneau fini. Un quotient d'une de ces algèbres sera également complètement P-calculable lorsque l'idéal noyau est une partie P-détachable de l'algèbre des polynômes.
Il semble très improbable que la clôture algébrique de Q puisse être présentée de manière complètement P-calculable; nous donnons néanmoins un exemple (en B.g) d'extension algébrique infinie de Q présentée de manière que l'addition et le produit y soient complètement P-calculables.
Dans la section C, qui peut être lue à peu près indépendamment de la section B, l'objectif est de montrer que l'algèbre linéaire "classique" est une algèbre en temps polynomial.
Nous construisons un bon stock d'anneaux commutatifs sur lesquels "le calcul des déterminants est en temps polynomial", à peu de chose près les mêmes que ceux qui ont été montrés complètement P-calculables dans la partie B. Nous mettons en évidence le lien étroit entre la calculabilité des déterminants en temps polynomial d'une part et la calculabilité du produit d'une liste de matrices en temps polynomial d'autre part.
Enfin, nous étudions en détail la méthode du pivot améliorée à la Bareiss et sa calculabilité en temps polynomial.

Computability in countable algebraic structures

Abstract :

We study the computability in discrete enumerable algebraic structures from the viewpoint of a given class of constructions C. Our walk is to relativize for the class C the methods of constructive mathematics. The most important class we study is P : the class of polynomial time computable functions.
We introduce the notion of completely C-computable algebraic structure (the C-computability of evaluation of formulas). We prove that the most elementary algebraic structures are completely P-computable in a natural sense.
For example the natural completely P-computable presentation of the ring of polynomials with integer coefficients is the usual one (dense presentation with integers in binary).
We study the P-computability of linear algebra. For commutative rings, we give strong links between the three notions:
- P-computability of determinants
- P-computability of the product of a list of matrices
- P-computability of addition, multiplication, exact division, and P-majoration of determinants (in the case of an integral domain). (these links are often given for the arithmetic complexity only).