Safe Recursion Over an Arbitrary Structure: PAR, PH and DPH

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

Full description

Saved in:
Bibliographic Details
Published in:Electronic notes in theoretical computer science 2003-11, Vol.90, p.3-14
Main Authors: Bournez, Olivier, Cucker, Felipe, de Naurois, Paulin Jacobé, Marion, Jean-Yves
Format: Article
Language:English
Subjects:
Complexity
computability
parallel polynomial time
sequential polynomial time
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1571-0661
1571-0661
DOI:10.1016/S1571-0661(03)00005-7