Implicit Complexity over an Arbitrary Structure: Sequential and Parallel Polynomial Time

DOI10.1093/logcom/exh036zbMath1077.03021WikidataQ57733215 ScholiaQ57733215MaRDI QIDQ4673356

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

Publication date: 29 April 2005

Published in: Journal of Logic and Computation (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/7f4a4a82896b8f7d8b8e1007a27fbdfdc405e0e4

zbMATH Keywords

complexity theory; Blum-Shub-Smale model; function algebras

Mathematics Subject Classification ID

03D15: Complexity of computation (including implicit computational complexity)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

03D20: Recursive functions and relations, subrecursive hierarchies

03D75: Abstract and axiomatic computability and recursion theory

Related Items

Simulation of simultaneous safe recursion over an arbitrary structure, Exotic quantifiers, complexity classes, and complete problems, Implicit complexity over an arbitrary structure: Quantifier alternations