Completeness results and syntactic characterizations of complexity classes over arbitrary structures

Résultats de complétude et caractérisations syntaxiques de classes de complexité sur des structures arbitraires

Paulin Jacobé de Naurois (1)

1 LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications

We focus on the BSS model of computation over arbitrary structures. We provide new completeness results for geometrical problems when this structure is the set of real numbers with addition and order. We also provide several machine independent characterizations of complexity classes over arbitrary structures. We extend some results by Gradel, Gurevich and Meer in descriptive complexity, characterizing deterministic and non deterministic polynomial.time decision problems in terms of logics over metaflnite structures. We extend some results by Bellantoni and Cook, characterizing functions computable in sequential determinisitc polynomial time, and by Leivant and Marion, characterizing functions computable in parallel determinisitc polynomial time in terms of algebras of recursive functions. We also provide some characterizations of functions computable within the polynomial hierarchy and in polynomial alternating time.

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.

Mots clés: BSS model of computation; Algebraic complexity; Descriptive complexity; Imlpicitecomplexity; Logic; Algebra of recursive functions.

Mots clés: Modèle de calcul BSS; Complexité algébrique; Complexité descriptive; Complexité implicite; Logique; Algèbres de fonctions récursives.; Complexité de calcul (informatique); Fonctions récursives; Mathématiques -- Informatique

Domaines: Autre [cs.OH]

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⟩