Complexity invariance of real interpretations

Abstract : In the field of implicit computational complexity, we are con- sidering in this paper the fruitful branch of interpretation methods. In this area, the synthesis problem is solved by Tarski's decision procedure, and consequently interpretations are usually chosen over the reals rather than over the integers. Doing so, one cannot use anymore the (good) properties of the natural (well-) ordering of N employed to bound the complexity of programs. We show that, actually, polynomials over the reals benefit from some properties that allow their safe use for complex- ity. We illustrate this by two characterizations, one of PTIME and one of PSPACE.
Type de document :
Communication dans un congrès
Jan Kratochvi, Angsheng Li, Jiri Fiala and Petr Kolman. 7th Annual Conference on Theory and Applications of Models of Computation - TAMC 2010, Jun 2010, Prague, Czech Republic. Springer, 6108, pp.139-150, 2010, Lecture Notes in Computer Science. 〈10.1007/978-3-642-13562-0〉
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00535784
Contributeur : Guillaume Bonfante <>
Soumis le : vendredi 12 novembre 2010 - 17:06:17
Dernière modification le : vendredi 14 septembre 2018 - 09:16:05
Document(s) archivé(s) le : vendredi 26 octobre 2012 - 15:31:01

Fichier

final.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Guillaume Bonfante, Florian Deloup. Complexity invariance of real interpretations. Jan Kratochvi, Angsheng Li, Jiri Fiala and Petr Kolman. 7th Annual Conference on Theory and Applications of Models of Computation - TAMC 2010, Jun 2010, Prague, Czech Republic. Springer, 6108, pp.139-150, 2010, Lecture Notes in Computer Science. 〈10.1007/978-3-642-13562-0〉. 〈inria-00535784〉

Partager

Métriques

Consultations de la notice

229

Téléchargements de fichiers

193