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

DOI10.2307/421100zbMATH Open0931.03058OpenAlexW1992139964MaRDI QIDQ4382502FDOQ4382502

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

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

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)

Cites Work

• Title not available (Why is that?)
• A new recursion-theoretic characterization of the polytime functions
• Logical relations and the typed λ-calculus
• Functional interpretations of feasibly constructive arithmetic
• Provably total functions of intuitionistic bounded arithmetic

Cited In (8)

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

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)