Implicit complexity over an arbitrary structure: Quantifier alternations

DOI10.1016/J.IC.2005.07.005MaRDI QIDQ2490113zbMATH OpenOpenAlexWikidataFDO

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

Arbitrary structuresBSS computationImplicit complexitySafe recursion

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 2163035
• Safe recursion over an arbitrary structure: PAR, PH and DPH
• Implicit Complexity over an Arbitrary Structure: Sequential and Parallel Polynomial Time
• scientific article; zbMATH DE number 1956513
• Implicit recursion-theoretic characterizations of counting classes

Cites work

• A new recursion-theoretic characterization of the polytime functions
• scientific article; zbMATH DE number 1696756 (Why is no real title available?)
• scientific article; zbMATH DE number 445159 (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 2079048 (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?)
• scientific article; zbMATH DE number 806752 (Why is no real title available?)
• Implicit Complexity over an Arbitrary Structure: Sequential and Parallel Polynomial Time
• Logics which capture complexity classes over the reals
• On the Complexity of Quantifier Elimination: the Structural Approach
• Tailoring recursion for complexity
• The expressive power of higher-order types or, life without CONS
• The Logic of Choice

Cited in

(7)

• scientific article; zbMATH DE number 1956513 (Why is no real title available?)
• Computation over algebraic structures and a classification of undecidable problems
• Implicit Complexity over an Arbitrary Structure: Sequential and Parallel Polynomial Time
• scientific article; zbMATH DE number 2163035 (Why is no real title available?)
• Safe recursion over an arbitrary structure: PAR, PH and DPH
• On relativizations of the P =? NP question for several structures
• Simulation of Turing machines with analytic discrete ODEs: polynomial-time and space over the reals characterised with discrete ordinary differential equations

This page was built for publication: Implicit complexity over an arbitrary structure: Quantifier alternations

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