Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-17T22:26:15.233Z Has data issue: false hasContentIssue false

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

Published online by Cambridge University Press:  15 January 2014

Martin Hofmann*
Affiliation:
Fachbereich Mathematik, Technische Universität Darmstadt, Schlossgartenstrasse 7, 64289 Darmstadt, Germany. E-mail: mh@mathematik.tu-darmstadt.de

Abstract

We use the category of presheaves over PTIME-functions in order to show that Cook and Urquhart's higher-order function algebra PV ω defines exactly the PTIME-iunctions. As a byproduct we obtain a syntax-free generalisation of PTIME-computability to higher types.

By restricting to sheaves for a suitable topology we obtain a model for intuitionistic predicate logic with -induction over PV ω and use this to re-establish that the provably total functions in this system are polynomial time computable. Finally, we apply the category-theoretic approach to a new higher-order extension of Bellantoni-Cook's system BC of safe recursion.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1997

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable