Polynomial time operations in explicit mathematics

DOI10.2307/2275547zbMath0891.03023OpenAlexW2119127687MaRDI QIDQ4358055

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

proof-theoretic strengthGrzegorczyk classesprovably total functionspolytime computationpolynomial time computable arithmeticself-applicative operations

Mathematics Subject Classification ID

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

Related Items (2)

Theories with self-application and computational complexity. ⋮ Elementary explicit types and polynomial time operations

Cites Work

• Unnamed Item
• Unnamed Item
• Functional interpretations of feasibly constructive arithmetic
• Constructivism in mathematics. An introduction. Volume I
• Systems of explicit mathematics with non-constructive \(\mu\)-operator. I
• Totality in applicative theories
• Hilbert's program relativized; Proof-theoretical and foundational reductions
• A feasible theory for analysis
• Asymmetric Interpretations for Bounded Theories

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