Implicit complexityover an arbitrarystructure: Quantifier alternations

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

doi:10.1016/j.ic.2005.07.005

Author(s)

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

Related Research Unit(s)

Department of Mathematics

Detail(s)

Original language	English
Pages (from-to)	210-230
Journal / Publication	Information and Computation
Volume	204
Issue number	2
Publication status	Published - Feb 2006

Link(s)

DOI	DOI https://doi.org/10.1016/j.ic.2005.07.005 Final Published version
	Check@CityULib
Link to Scopus	https://www.scopus.com/record/display.uri?eid=2-s2.0-84855200443&origin=recordpage
Permanent Link	https://scholars.cityu.edu.hk/en/publications/publication(67a4a323-90dd-4c6b-a3ae-b8fb788cebe5).html

Abstract

We provide machine-independent characterizations of some complexityclasses, over an arbitrarystructure, in the model of computation proposed by L. Blum, M. Shub and S. Smale. We show that the levels of the polynomial hierarchy correspond to safe recursion with predicative minimization and the levels of the digital polynomial hierarchy to safe recursion with digital predicative minimization. Also, we show that polynomial alternating time corresponds to safe recursion with predicative substitutions and that digital polynomial alternating time corresponds to safe recursion with digital predicative substitutions. © 2005 Elsevier Inc. All rights reserved.

Research Area(s)

Arbitrary structures, BSS computation, Implicit complexity, Safe recursion

Citation Format(s)

[ RIS ] [ BibTeX ]

Implicit complexityover an arbitrarystructure: Quantifier alternations. / Bournez, Olivier; Cucker, Felipe; De Naurois, Paulin Jacobé et al.
In: Information and Computation, Vol. 204, No. 2, 02.2006, p. 210-230.

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

Bournez, O, Cucker, F, De Naurois, PJ & Marion, J-Y 2006, 'Implicit complexityover an arbitrarystructure: Quantifier alternations', Information and Computation, vol. 204, no. 2, pp. 210-230. https://doi.org/10.1016/j.ic.2005.07.005

Bournez, O., Cucker, F., De Naurois, P. J., & Marion, J.-Y. (2006). Implicit complexityover an arbitrarystructure: Quantifier alternations. Information and Computation, 204(2), 210-230. https://doi.org/10.1016/j.ic.2005.07.005

Bournez O, Cucker F, De Naurois PJ, Marion JY. Implicit complexityover an arbitrarystructure: Quantifier alternations. Information and Computation. 2006 Feb;204(2):210-230. doi: 10.1016/j.ic.2005.07.005

Bournez, Olivier ; Cucker, Felipe ; De Naurois, Paulin Jacobé et al. / Implicit complexityover an arbitrarystructure : Quantifier alternations. In: Information and Computation. 2006 ; Vol. 204, No. 2. pp. 210-230.

Implicit complexityover an arbitrarystructure : Quantifier alternations