Safe recursion over an arbitrary structure : PAR, PH and DPH

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)22_Publication in policy or professional journal

2 Scopus Citations
View graph of relations

Author(s)

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

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)3-14
Journal / PublicationElectronic Notes in Theoretical Computer Science
Volume90
Publication statusPublished - 28 Nov 2003

Conference

TitleProceedings of the Fifth International Workshop on Implicit Computational Complexity
PlaceCanada
CityOttawa
Period26 - 27 June 2003

Link(s)

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. © 2003 Elsevier B.V. All rights reserved.

Research Area(s)

  • Complexity, Computability, Parallel polynomial time, Sequential polynomial time

Citation Format(s)

Safe recursion over an arbitrary structure: PAR, PH and DPH. / Bournez, Olivier; Cucker, Felipe; De Naurois, Paulin Jacobé et al.
In: Electronic Notes in Theoretical Computer Science, Vol. 90, 28.11.2003, p. 3-14.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)22_Publication in policy or professional journal

Download Statistics

No data available