Implicit complexity over an arbitrary structure: Sequential and parallel polynomial time

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

doi:10.1093/logcom/exh036

Implicit complexity over an arbitrary structure: Sequential and parallel polynomial time

Olivier Bournez
, Felipe Cucker
, Paulin Jacobé De Naurois
, Jean Yves Marion

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Pages (from-to)	41-58
Number of pages	18
Journal	Journal of Logic and Computation
Volume	15
Issue number	1
DOIs	https://doi.org/10.1093/logcom/exh036
Publication status	Published - 1 Feb 2005
Externally published	Yes

Keywords

Blum
Complexity theory
Implicit complexity
Shub
Smale model

Access to Document

10.1093/logcom/exh036

Cite this

@article{2c38d463136c4bceaf58e0339e2b9b26,

title = "Implicit complexity over an arbitrary structure: Sequential and parallel polynomial time",

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, Complexity theory, Implicit complexity, Shub, Smale model",

author = "Olivier Bournez and Felipe Cucker and \{De Naurois\}, \{Paulin Jacob{\'e}\} and Marion, \{Jean Yves\}",

year = "2005",

month = feb,

day = "1",

doi = "10.1093/logcom/exh036",

language = "English",

volume = "15",

pages = "41--58",

journal = "Journal of Logic and Computation",

issn = "0955-792X",

number = "1",

}

TY - JOUR

T1 - Implicit complexity over an arbitrary structure

T2 - Sequential and parallel polynomial time

AU - Bournez, Olivier

AU - Cucker, Felipe

AU - De Naurois, Paulin Jacobé

AU - Marion, Jean Yves

PY - 2005/2/1

Y1 - 2005/2/1

N2 - 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.

AB - 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.

KW - Blum

KW - Complexity theory

KW - Implicit complexity

KW - Shub

KW - Smale model

UR - https://www.scopus.com/pages/publications/15744376022

U2 - 10.1093/logcom/exh036

DO - 10.1093/logcom/exh036

M3 - Article

AN - SCOPUS:15744376022

SN - 0955-792X

VL - 15

SP - 41

EP - 58

JO - Journal of Logic and Computation

JF - Journal of Logic and Computation

IS - 1

ER -

Implicit complexity over an arbitrary structure: Sequential and parallel polynomial time

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this