| Titre: |
Résultats de
Complétude et Caractérisations Syntaxiques de Classes de
Complexité sur des Structures Arbitraires |
| Soutenue le: |
15 décembre 2004,
à Hong Kong |
| Dirigée par: |
Dr. Olivier Bournez,
chargé
de recherches INRIA au LORIA
|
|
Pr. Jean-Yves
Marion, professeur à l'INPL
|
|
Pr. Felipe Cucker, professeur
à City University of Hong Kong
|
| Jury: |
Dr. Olivier Bournez (LORIA)
|
|
Dr. Siu Wing Cheng (Hong Kong
University of Science and Technology)
|
|
Pr. Felipe Cucker (City
University of Hong Kong)
|
|
Dr. Mordecai Golin (Hong Kong
University of Science and Technology) |
|
Pr. Jean-Yves Marion (INPL,
LORIA)
|
|
Dr. DingXuan Zhou (City
University of Hong Kong) |
| Après avis de: |
Dr. Mordecai Golin (Hong Kong
University of Science and Technology) |
|
Pr. Pascal Koiran (Ecole Normale
Supérieure de Lyon)
|
|
Pr. Michel de Rougemont
(Université Paris II)
|
|
Dr. DingXuan Zhou (City
University of Hong Kong) |
| Résumé: |
Nous nous plaçons dans le
modèle de calcul BSS sur des structures
arbitraires. Nous présentons de nouveaux résultats de
complétude
concernant des problèmes géométriques sur les
nombres réels
avec addition et ordre. Nous présentons aussi plusieurs
caractérisations de classes de complexité
indépendantes du
modèle de calcul sous-jacent. Nous étendons des
résultats de
Grädel, Gurevich et Meer en complexité descriptive, qui
caractérisent les problèmes de décisions
calculables en temps
polynomial déterministe et non-déterministe en termes de
logique sur des structures
métafinies. Nous étendons des résultats de
Bellantoni et Cook
pour caractériser les fonctions calculables en temps polynomial
séquentiel, et de Leivant et Marion pour caractéeriser
les fonctions
calculables en temps polynomial parallèle, en termes
d'algèbres de
fonctions récursives. Nous présentons également
des
caractérisations de fonctions calculables dans la
hiérarchie
polynomiale et en temps polynomial alternant. |
| Mots clés: |
modèle de calcul BSS,
complexité algébrique, complexité
descriptive, complexité implicite, logique, algèbres de
fonctions
récursives. |