Polynomial time operations in explicit mathematics

DOI10.2307/2275547MaRDI QIDQ4358055zbMATH OpenOpenAlexFDO

Authors Thomas Strahm

Publication date 28 September 1997

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2307/2275547

zbMATH Keywords

Grzegorczyk classespolynomial time computable arithmeticpolytime computationproof-theoretic strengthprovably total functionsself-applicative operations

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Proof theory in general (including proof-theoretic semantics) (03F03) First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Elementary explicit types and polynomial time operations
• Realisability in weak systems of explicit mathematics
• scientific article; zbMATH DE number 4139739
• Polytime, combinatory logic and positive safe induction

Cites work

• A feasible theory for analysis
• Asymmetric Interpretations for Bounded Theories
• Constructivism in mathematics. An introduction. Volume I
• Functional interpretations of feasibly constructive arithmetic
• Hilbert's program relativized; Proof-theoretical and foundational reductions
• scientific article; zbMATH DE number 3900744 (Why is no real title available?)
• scientific article; zbMATH DE number 3577197 (Why is no real title available?)
• Systems of explicit mathematics with non-constructive \(\mu\)-operator. I
• Totality in applicative theories

Cited in

(11)

• Polytime, combinatory logic and positive safe induction
• Theories with self-application and computational complexity.
• A feasible theory of truth over combinatory algebra
• Polynomial Time Algorithms for Finding Integer Relations among Real Numbers
• Realisability in weak systems of explicit mathematics
• scientific article; zbMATH DE number 4139739 (Why is no real title available?)
• scientific article; zbMATH DE number 4160708 (Why is no real title available?)
• Elementary explicit types and polynomial time operations
• Feasible Operations and Applicative Theories Based on λη
• Admissible closures of polynomial time computable arithmetic
• The provably terminating operations of the subsystem PETJ of explicit mathematics

This page was built for publication: Polynomial time operations in explicit mathematics

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