HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 metadata

https://hal.inria.fr/inria-00099619
Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 9:39:28 AM
Last modification on : Friday, May 13, 2022 - 10:18:05 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

117