| Title: |
Completeness Results and
Syntactic Characterizations of Complexity Classes over Arbitrary
Structures |
| Defended on: |
Decembre 15th, 2004, in Hong Kong |
| Supervisors: |
Dr. Olivier Bournez,
chargé
de recherches INRIA (LORIA)
|
|
Pr. Jean-Yves
Marion (INPL, LORIA)
|
|
Pr. Felipe Cucker (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) |
| Referees: |
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) |
| 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 Grädel, Gurevich and Meer in
descriptive complexity, characterizing deterministic and non
deterministic polynomial time decision problems in terms of logics over
metafinite 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. |
Keywords
|
BSS model of computation,
algebraic complexity, descriptive complexity, imlpicitecomplexity,
logic, algebra of recursive functions. |