Skip to Main content Skip to Navigation
Conference papers

Characterizations of Polynomial Complexity Classes with a Better Intensionality

Jean-Yves Marion 1 Romain Péchoux 1
1 CARTE - Theoretical adverse computations, and safety
LORIA - FM - Department of Formal Methods , Inria Nancy - Grand Est
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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download
Contributor : Romain Péchoux <>
Submitted on : Monday, October 20, 2008 - 6:05:56 PM
Last modification on : Tuesday, May 5, 2020 - 5:02:15 PM
Long-term archiving on: : Monday, June 7, 2010 - 7:01:26 PM


Publisher files allowed on an open archive




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⟩



Record views


Files downloads