Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/inria-00099619
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 9:39:28 AM
Last modification on : Tuesday, May 5, 2020 - 5:02:07 PM

Identifiers

  • HAL Id : inria-00099619, version 1

Collections

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, 13 p. ⟨inria-00099619⟩

Share

Metrics

Record views

289