An Application of Category-Theoretic Semantics to the Characterisation of Complexity Classes Using Higher-Order Function Algebras

DOI10.2307/421100zbMath0931.03058OpenAlexW1992139964MaRDI QIDQ4382502

Martin Hofmann

Publication date: 28 February 2000

Published in: Bulletin of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/07c6705c9d818bad9c6927aa4ddddce1c44839a0

zbMATH Keywords

computable functionspolynomial timeintuitionistic predicate logicsafe recursionprovably total functionscategory of presheaves over PTIME-functionsgeneralisation of PTIME-computability to higher typeshigher-order function algebra

Mathematics Subject Classification ID

Categorical logic, topoi (03G30) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Presheaves and sheaves, stacks, descent conditions (category-theoretic aspects) (18F20) Combinatory logic and lambda calculus (03B40) Higher-type and set recursion theory (03D65)

Related Items (2)

Safe recursion with higher types and BCK-algebra ⋮ Implicit computation complexity in higher-order programming languages

Cites Work

• Unnamed Item
• Functional interpretations of feasibly constructive arithmetic
• A new recursion-theoretic characterization of the polytime functions
• Logical relations and the typed λ-calculus
• Provably total functions of intuitionistic bounded arithmetic

This page was built for publication: An Application of Category-Theoretic Semantics to the Characterisation of Complexity Classes Using Higher-Order Function Algebras