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

DOI10.2307/421100MaRDI QIDQ4382502zbMATH OpenOpenAlexFDO

Authors Martin Hofmann

Publication date 28 February 2000

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

Full work available at URL https://semanticscholar.org/paper/07c6705c9d818bad9c6927aa4ddddce1c44839a0, http://www.math.ucla.edu/~asl/bsl/0304-toc.htm

zbMATH Keywords

polynomial timecomputable functionssafe recursionprovably total functionsintuitionistic predicate logiccategory of presheaves over PTIME-functionsgeneralisation of PTIME-computability to higher typeshigher-order function algebra

Mathematics Subject Classification ID

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

Recommendations

• Timed Sets, Functional Complexity, and Computability
• Game semantics approach to higher-order complexity
• scientific article; zbMATH DE number 65741
• A note on complexity measures for inductive classes in constructive type theory

Cites work

• scientific article; zbMATH DE number 3959364 (Why is no real title available?)
• A new recursion-theoretic characterization of the polytime functions
• Functional interpretations of feasibly constructive arithmetic
• Logical relations and the typed λ-calculus
• Provably total functions of intuitionistic bounded arithmetic

Cited in

(8)

• The complexity space of partial functions: a connection between complexity analysis and denotational semantics
• Implicit computation complexity in higher-order programming languages
• A categorical framework for congruence of applicative bisimilarity in higher-order languages
• V-comprehensions and P space
• Safe recursion with higher types and BCK-algebra
• Some fundamental algebraic tools for the semantics of computation. III: Indexed categories
• A categorical setting for lower complexity
• Game semantics approach to higher-order complexity

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4382502)