Safe Recursion Over an Arbitrary Structure: PAR, PH and DPH

Olivier Bournez 1 Felipe Cucker Paulin Jacobé de Naurois 1 Jean-Yves Marion 2
1 PROTHEO - Constraints, automatic deduction and software properties proofs
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
2 CALLIGRAMME - Linear logic, proof networks and categorial grammars
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Considering the Blum, Shub, and Smale computational model for real numbers, extended by Poizat to general structures, classical complexity can be considered as the restriction to finite structures of a more general notion of computability and complexity working over arbitrary structures. In a previous paper, we showed that the machine-independent characterization of Bellantoni and Cook of sequential polynomial time for classical complexity is actually the restriction to finite structures of a characterization of sequential polynomial time over arbitrary structures. In this paper, we prove that the same phenomenon happens for several other complexity classes: over arbitrary structures, parallel polynomial time corresponds to safe recursion with substitutions, and the polynomial hierarchy corresponds to safe recursion with predicative minimization. Our results yield machine-independent characterizations of several complexity classes subsuming previous ones when restricted to finite structures.
Mots-clés : complexité safe recursion complexity blum shub smale model modèle blum shub smale récursion sûre
Type de document :
Communication dans un congrès
Fifth International Workshop on Implicit Computational Complexity - ICC'2003, Jun 2003, Ottawa, Canada, 90/1 (1), 13 p, 2003, Electronic Notes in Computer Science
Liste complète des métadonnées
https://hal.inria.fr/inria-00099619
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 09:39:28
Dernière modification le : jeudi 11 janvier 2018 - 06:19:58

Identifiants

  • HAL Id : inria-00099619, version 1

Collections

INRIA | LORIA | UNIV-LORRAINE

Citation

Olivier Bournez, Felipe Cucker, Paulin Jacobé de Naurois, Jean-Yves Marion. Safe Recursion Over an Arbitrary Structure: PAR, PH and DPH. Fifth International Workshop on Implicit Computational Complexity - ICC'2003, Jun 2003, Ottawa, Canada, 90/1 (1), 13 p, 2003, Electronic Notes in Computer Science. 〈inria-00099619〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

257

Contact


archive-ouverte@inria.fr