3527 articles – 5249 Notices  [english version]

hal-00644361, version 1

Algebraic Characterizations of Complexity-Theoretic Classes of Real Functions

Olivier Bournez () a1, Walid Gomaa () b2, Emmanuel Hainry () c3

International Journal of Unconventional Computing 7, 5 (2011) 331-351

Résumé : Recursive analysis is the most classical approach to model and discuss computations over the real numbers.Recently, it has been shown that computability classes of functions in the sense of recursive analysis can be defined (or characterized) in an algebraic machine independent way, without resorting to Turing machines. In particular nice connections between the class of computable functions (and some of its sub- and sup-classes) over the reals and algebraically defined (sub- and sup-) classes of R-recursive functions à la Moore 96 have been obtained. However, until now, this has been done only at the computability level, and not at the complexity level. In this paper we provide a framework that allows us to dive into the complexity level of real functions. In particular we provide the first algebraic characterization of polynomial-time computable functions over the reals. This framework opens the field of implicit complexity of analog functions, and also provides a new reading of some of the existing characterizations at the computability level.

  • a –  Polytechnique - X
  • b –  Egypt-Japan University of Science and Technology
  • c –  Université Henri Poincaré - Nancy I
  • 1 :  Laboratoire d'informatique de l'école polytechnique (LIX)
  • CNRS : UMR7161 – Polytechnique - X
  • 2 :  Faculty of Engineering, Alexandria University
  • Alexandria University
  • 3 :  CARTE (INRIA Nancy - Grand Est / LORIA)
  • CNRS : UMR7503 – INRIA – Université de Lorraine
  • Domaine : Informatique/Complexité
  • Mots-clés : Recursive Analysis – Polynomial Time – Algebraic Characterization – Real Computation – Oracle Turing Machines
  • Commentaire : Accepted for publication in International Journal of Unconventional Computing
 
  • hal-00644361, version 1
  • oai:hal.inria.fr:hal-00644361
  • Contributeur : 
  • Soumis le : Jeudi 24 Novembre 2011, 11:51:55
  • Dernière modification le : Jeudi 31 Janvier 2013, 11:00:25