Completeness results and syntactic characterizations of complexity classes over arbitrary structures
Paulin Jacobé de Naurois · 2004
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.