Characterizations of Polynomial Complexity Classes with a Better Intensionality - Archive ouverte HAL Access content directly
Conference Papers Year : 2008

Characterizations of Polynomial Complexity Classes with a Better Intensionality

(1) , (1)
1

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.
Fichier principal
Vignette du fichier
ppdp09-pechoux.pdf (252.55 Ko) Télécharger le fichier
Origin : Publisher files allowed on an open archive
Loading...

Dates and versions

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

Identifiers

Cite

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⟩
109 View
114 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More