Polytime, combinatory logic and positive safe induction
From MaRDI portal
Publication:1407533
DOI10.1007/S001530100105zbMath1042.03015OpenAlexW2032152194MaRDI QIDQ1407533
Publication date: 16 September 2003
Published in: Archive for Mathematical Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s001530100105
Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Metamathematics of constructive systems (03F50) Combinatory logic and lambda calculus (03B40)
Related Items (11)
The provably terminating operations of the subsystem PETJ of explicit mathematics ⋮ Theories with self-application and computational complexity. ⋮ Primitive recursive selection functions for existential assertions over abstract algebras ⋮ Pointwise Transfinite Induction and a Miniaturized Predicativity ⋮ A proof-theoretic characterization of the basic feasible functionals ⋮ Tiered Arithmetics ⋮ Elementary explicit types and polynomial time operations ⋮ On the proof theory of type two functionals based on primitive recursive operations ⋮ Realisability in weak systems of explicit mathematics ⋮ Implicit recursion-theoretic characterizations of counting classes ⋮ Applicative theories for logarithmic complexity classes
This page was built for publication: Polytime, combinatory logic and positive safe induction
