Implicit complexity over an arbitrary structure: Quantifier alternations

DOI10.1016/j.ic.2005.07.005zbMath1093.68041WikidataQ57733184 ScholiaQ57733184MaRDI QIDQ2490113

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

Publication date: 28 April 2006

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/inria-00107811/file/A04-R-300.pdf

zbMATH Keywords

Safe recursion; Arbitrary structures; BSS computation; Implicit complexity

Mathematics Subject Classification ID

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

Related Items

Computation over algebraic structures and a classification of undecidable problems, On Relativizations of the P =? NP Question for Several Structures

Cites Work

• A new recursion-theoretic characterization of the polytime functions
• The expressive power of higher-order types or, life without CONS
• On the Complexity of Quantifier Elimination: the Structural Approach
• Logics which capture complexity classes over the reals
• The Logic of Choice
• Implicit Complexity over an Arbitrary Structure: Sequential and Parallel Polynomial Time
• Tailoring recursion for complexity
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item