Implicit Complexity Over an Arbitrary Structure: Sequential and Parallel Polynomial Time.

Olivier Bournez; Felipe Cucker; Paulin Jacobé de Naurois; Jean-Yves Marion

Journal articles

Implicit Complexity Over an Arbitrary Structure: Sequential and Parallel Polynomial Time.

Olivier Bournez ¹ Felipe Cucker Paulin Jacobé de Naurois Jean-Yves Marion ²

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 : We provide several machine-independent characterizations of deterministic complexity classes in the model of computation proposed by L. Blum, M. Shub and S. Smale. We provide a characterization of partial recursive functions over any arbitrary structure. We show that polynomial time over an arbitrary structure can be characterized in terms of safe recursion. We show that polynomial parallel time over an arbitrary structure can be characterized in terms of safe recursion with substitutions.

Keywords : Blum Shub Smale model implicit complexity complexity theory

Document type :

Journal articles

Domain :

Computer Science [cs] / Computational Complexity [cs.CC]

Complete list of metadata

https://hal.inria.fr/inria-00102942
Contributor : Olivier Bournez Connect in order to contact the contributor
Submitted on : Monday, October 2, 2006 - 10:06:19 PM
Last modification on : Friday, May 13, 2022 - 10:18:04 PM

Implicit Complexity Over an Arbitrary Structure: Sequential and Parallel Polynomial Time.

Identifiers

Collections

Citation

Export

Metrics

251

Contact Legal Notice Personal Data

Implicit Complexity Over an Arbitrary Structure: Sequential and Parallel Polynomial Time.

Identifiers

Collections

Citation

Export

Share

Metrics

251

Contact Legal Notice Personal Data