Characterizations of Polynomial Complexity Classes with a Better Intensionality - INRIA - Institut National de Recherche en Informatique et en Automatique Accéder directement au contenu
Communication Dans Un Congrès Année : 2008

Characterizations of Polynomial Complexity Classes with a Better Intensionality

Résumé

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.
Fichier principal
Vignette du fichier
ppdp09-pechoux.pdf (252.55 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

inria-00332389 , version 1 (20-10-2008)

Identifiants

Citer

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, Universidad Polytechnica, Jul 2008, Valencia, Spain. pp.79-88, ⟨10.1145/1389449.1389460⟩. ⟨inria-00332389⟩
112 Consultations
138 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More