Skip to Main content Skip to Navigation
Theses

Completeness results and syntactic characterizations of complexity classes over arbitrary structures

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 Gradel, 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ériser 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.
Document type :
Theses
Complete list of metadatas

https://hal.univ-lorraine.fr/tel-01749690
Contributor : Thèses Ul <>
Submitted on : Thursday, March 29, 2018 - 12:23:34 PM
Last modification on : Tuesday, April 24, 2018 - 1:31:01 PM
Document(s) archivé(s) le : Friday, September 14, 2018 - 9:55:57 AM

File

INPL_T_2004_JACOBE_DE_NAUROIS_...
Files produced by the author(s)

Identifiers

  • HAL Id : tel-01749690, version 1

Collections

Citation

Paulin Jacobé de Naurois. Completeness results and syntactic characterizations of complexity classes over arbitrary structures. Other [cs.OH]. Institut National Polytechnique de Lorraine, 2004. English. ⟨NNT : 2004INPL112N⟩. ⟨tel-01749690⟩

Share

Metrics

Record views

62

Files downloads

27