Polytime, combinatory logic and positive safe induction

DOI10.1007/s001530100105zbMath1042.03015MaRDI QIDQ1407533

Andrea Cantini

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

zbMATH Keywords

combinatory logic; restricted induction; polytime

Mathematics Subject Classification ID

03D15: Complexity of computation (including implicit computational complexity)

03F30: First-order arithmetic and fragments

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

03F50: Metamathematics of constructive systems

03B40: Combinatory logic and lambda calculus

Related Items

Tiered Arithmetics, On the proof theory of type two functionals based on primitive recursive operations, The provably terminating operations of the subsystem PETJ of explicit mathematics, A proof-theoretic characterization of the basic feasible functionals, Primitive recursive selection functions for existential assertions over abstract algebras, Theories with self-application and computational complexity., Implicit recursion-theoretic characterizations of counting classes, Applicative theories for logarithmic complexity classes, Realisability in weak systems of explicit mathematics, Pointwise Transfinite Induction and a Miniaturized Predicativity, Elementary explicit types and polynomial time operations