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

DOI10.1016/S1571-0661(03)00005-7MaRDI QIDQ4916232zbMATH OpenOpenAlexWikidataFDO

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

Publication date 19 April 2013

Published in Electronic Notes in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s1571-0661(03)00005-7

zbMATH Keywords

complexitycomputabilityparallel polynomial timesequential polynomial time

Mathematics Subject Classification ID

Computation over the reals, computable analysis (03D78) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Recommendations

• scientific article; zbMATH DE number 1956513
• Implicit Complexity over an Arbitrary Structure: Sequential and Parallel Polynomial Time
• Implicit complexity over an arbitrary structure: Quantifier alternations
• scientific article; zbMATH DE number 2163035
• Safe recursive set functions

Cites work

• A new recursion-theoretic characterization of the polytime functions
• Accessible telephone directories
• scientific article; zbMATH DE number 1696756 (Why is no real title available?)
• scientific article; zbMATH DE number 3711948 (Why is no real title available?)
• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 1263207 (Why is no real title available?)
• scientific article; zbMATH DE number 1956513 (Why is no real title available?)
• scientific article; zbMATH DE number 4114603 (Why is no real title available?)
• scientific article; zbMATH DE number 781350 (Why is no real title available?)
• scientific article; zbMATH DE number 803291 (Why is no real title available?)
• scientific article; zbMATH DE number 806743 (Why is no real title available?)
• Metafinite model theory
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• The expressive power of higher-order types or, life without CONS

Cited in

(7)

• Implicit complexity over an arbitrary structure: Quantifier alternations
• scientific article; zbMATH DE number 1956513 (Why is no real title available?)
• Implicit Complexity over an Arbitrary Structure: Sequential and Parallel Polynomial Time
• scientific article; zbMATH DE number 2163035 (Why is no real title available?)
• On relativizations of the P =? NP question for several structures
• SAFE TURING MACHINES, GRZEGORCZYK CLASSES AND POLYTIME
• Simulation of simultaneous safe recursion over an arbitrary structure

This page was built for publication: Safe recursion over an arbitrary structure: PAR, PH and DPH

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