Polynomial time operations in explicit mathematics
DOI10.2307/2275547zbMath0891.03023OpenAlexW2119127687MaRDI QIDQ4358055
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
proof-theoretic strengthGrzegorczyk classesprovably total functionspolytime computationpolynomial time computable arithmeticself-applicative operations
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)
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