Characterizations of Polynomial Complexity Classes with a Better Intensionality

Jean-Yves Marion 1 Romain Péchoux 1
1 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : In this paper, we study characterizations of polynomial complexity classes using first order functional programs and we try to improve their intensionality, that is the number of natural algorithms captured. We use polynomial assignments over the reals. The polynomial assignments used are inspired by the notions of quasi-interpretation and sup-interpretation, and are decidable when considering polynomials of bounded degree ranging over real numbers. Contrarily to quasi-interpretations, the considered assignments are not required to have the subterm property. Consequently, they capture a strictly larger number of natural algorithms (including quotient, gcd, duplicate elimination from a list) than previous characterizations using quasi-interpretations.
Type de document :
Communication dans un congrès
Proceedings of the 10th international ACM SIGPLAN conference on Principles and Practice of Declarative Programming - PPDP 2008, Jul 2008, Valencia, Spain. ACM, pp.79-88, 2008, 〈10.1145/1389449.1389460〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00332389
Contributeur : Romain Péchoux <>
Soumis le : lundi 20 octobre 2008 - 18:05:56
Dernière modification le : jeudi 11 janvier 2018 - 06:21:25
Document(s) archivé(s) le : lundi 7 juin 2010 - 19:01:26

Fichier

ppdp09-pechoux.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Collections

Citation

Jean-Yves Marion, Romain Péchoux. Characterizations of Polynomial Complexity Classes with a Better Intensionality. Proceedings of the 10th international ACM SIGPLAN conference on Principles and Practice of Declarative Programming - PPDP 2008, Jul 2008, Valencia, Spain. ACM, pp.79-88, 2008, 〈10.1145/1389449.1389460〉. 〈inria-00332389〉

Partager

Métriques

Consultations de la notice

286

Téléchargements de fichiers

104