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. © The Author, 2005. Published by Oxford University Press. All rights reserved.
| Original language | English |
|---|---|
| Pages (from-to) | 41-58 |
| Journal | Journal of Logic and Computation |
| Volume | 15 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - Feb 2005 |
Research Keywords
- Blum
- Complexity theory
- Implicit complexity
- Shub
- Smale model
Fingerprint
Dive into the research topics of 'Implicit complexity over an arbitrary structure: Sequential and parallel polynomial time'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver