Polynomial time operations in explicit mathematics

DOI10.2307/2275547zbMATH Open0891.03023OpenAlexW2119127687MaRDI QIDQ4358055FDOQ4358055

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

Recommendations

• Elementary explicit types and polynomial time operations
• Realisability in weak systems of explicit mathematics
• Publication:3472100
• Polytime, combinatory logic and positive safe induction

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (11)

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

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)