Characterizing complexity classes by higher type primitive recursive definitions

DOI10.1016/0304-3975(92)90363-KzbMath0779.68033MaRDI QIDQ1193623

Andreas Goerdt

Publication date: 27 September 1992

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

finite structuresfirst- order functionsGödel's system \(T\)Higher type primitive recursive definitionsinfinite syntactic hierarchy

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Proof theory in general (including proof-theoretic semantics) (03F03) Higher-type and set recursion theory (03D65)

Related Items (7)

Bounded combinatory logic and lower complexity ⋮ Computational Complexity Via Finite Types ⋮ Recursion in Higher Types and Resource Bounded Turing Machines ⋮ The Power of Non-determinism in Higher-Order Implicit Complexity ⋮ Complexity-theoretic hierarchies induced by fragments of Gödel's \(T\) ⋮ Realizability models for BLL-like languages ⋮ Implicit computation complexity in higher-order programming languages

Uses Software

• Nuprl

Cites Work

• LCF considered as a programming language
• On definition trees of ordinal recursive functionals: Reduction of the recursion orders by means of type level raising
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Characterizing complexity classes by higher type primitive recursive definitions