Computability over an Arbitrary Structure: Sequential and Parallel Polynomial Time

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

doi:10.1007/3-540-36576-1_12

Computability over an Arbitrary Structure: Sequential and Parallel Polynomial Time

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

City University of Hong Kong

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

15 Citations (Scopus)

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 computable functions over any arbitrary structure can be characterized in term of safe recursive functions. We show that polynomial parallel time decision problems over any arbitrary structure can be characterized in terms of safe recursive functions with substitutions. © Springer-Verlag Berlin Heidelberg 2003.

Original language	English
Pages (from-to)	185-199
Journal	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2620
DOIs	https://doi.org/10.1007/3-540-36576-1_12
Publication status	Published - 2003

Access Output

10.1007/3-540-36576-1_12

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{971bdc08a6764732a453a1d32292390f,

title = "Computability 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 computable functions over any arbitrary structure can be characterized in term of safe recursive functions. We show that polynomial parallel time decision problems over any arbitrary structure can be characterized in terms of safe recursive functions with substitutions. {\textcopyright} Springer-Verlag Berlin Heidelberg 2003.",

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

year = "2003",

doi = "10.1007/3-540-36576-1\_12",

language = "English",

volume = "2620",

pages = "185--199",

journal = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

issn = "0302-9743",

publisher = "Springer Science and Business Media Deutschland GmbH",

}

Computability over an Arbitrary Structure: Sequential and Parallel Polynomial Time. / Bournez, Olivier; Cucker, Felipe; de Naurois, Paulin Jacobé et al.
In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 2620, 2003, p. 185-199.

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

TY - JOUR

T1 - Computability 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 - 2003

Y1 - 2003

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 computable functions over any arbitrary structure can be characterized in term of safe recursive functions. We show that polynomial parallel time decision problems over any arbitrary structure can be characterized in terms of safe recursive functions with substitutions. © Springer-Verlag Berlin Heidelberg 2003.

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 computable functions over any arbitrary structure can be characterized in term of safe recursive functions. We show that polynomial parallel time decision problems over any arbitrary structure can be characterized in terms of safe recursive functions with substitutions. © Springer-Verlag Berlin Heidelberg 2003.

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

UR - https://www.scopus.com/pages/publications/21144447408#tab=impact

U2 - 10.1007/3-540-36576-1_12

DO - 10.1007/3-540-36576-1_12

M3 - RGC 21 - Publication in refereed journal

SN - 0302-9743

VL - 2620

SP - 185

EP - 199

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

ER -

Computability over an Arbitrary Structure: Sequential and Parallel Polynomial Time

Abstract

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this