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

DOI10.1093/LOGCOM/EXH036MaRDI QIDQ4673356zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Felipe Cucker, Paulin Jacobé de Naurois, Jean-Yves Marion, 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 theoryfunction algebrasBlum-Shub-Smale model

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Abstract and axiomatic computability and recursion theory (03D75)

Recommendations

• scientific article; zbMATH DE number 1956513
• scientific article; zbMATH DE number 2163035
• Implicit complexity over an arbitrary structure: Quantifier alternations
• Safe recursion over an arbitrary structure: PAR, PH and DPH
• On the computing power of +, -, and
• Function-algebraic characterizations of log and polylog parallel time
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• scientific article; zbMATH DE number 1354146
• scientific article; zbMATH DE number 1438912
• TIME BOUNDED COMPUTATIONS OVER THE REALS

Cited in

(9)

• scientific article; zbMATH DE number 1956513 (Why is no real title available?)
• Simulation of simultaneous safe recursion over an arbitrary structure
• scientific article; zbMATH DE number 2163035 (Why is no real title available?)
• Exotic quantifiers, complexity classes, and complete problems
• Simulation of Turing machines with analytic discrete ODEs: polynomial-time and space over the reals characterised with discrete ordinary differential equations
• Implicit complexity over an arbitrary structure: Quantifier alternations
• Languages and Compilers for Parallel Computing
• The complexity of computing in continuous time: space complexity is precision
• Safe recursion over an arbitrary structure: PAR, PH and DPH

This page was built for publication: Implicit Complexity over an Arbitrary Structure: Sequential and Parallel Polynomial Time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4673356)