Completeness results and syntactic characterizations of complexity classes over arbitrary structures

Abstract : 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.
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
Long-term archiving on : 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

30

Files downloads

12