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

DOI10.1016/S1571-0661(03)00005-7zbMath1261.68058OpenAlexW2040277600WikidataQ57733251 ScholiaQ57733251MaRDI QIDQ4916232

Paulin Jacobé de Naurois, Jean-Yves Marion, Felipe Cucker, 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

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

Related Items

On Relativizations of the P =? NP Question for Several Structures

Cites Work

• A new recursion-theoretic characterization of the polytime functions
• Metafinite model theory
• The expressive power of higher-order types or, life without CONS
• Accessible telephone directories
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item