Polynomial time operations in explicit mathematics

Journal of Symbolic Logic 62 (2):575-594 (1997)

In this paper we study (self)-applicative theories of operations and binary words in the context of polynomial time computability. We propose a first order theory PTO which allows full self-application and whose provably total functions on W = {0, 1} * are exactly the polynomial time computable functions. Our treatment of PTO is proof-theoretic and very much in the spirit of reductive proof theory
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2307/2275547
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 44,283
Through your library

References found in this work BETA

The Lambda Calculus. Its Syntax and Semantics.H. P. Barendregt - 1984 - Journal of Symbolic Logic 49 (1):301-303.
Totality in Applicative Theories.Gerhard Jäger & Thomas Strahm - 1995 - Annals of Pure and Applied Logic 74 (2):105-120.

View all 7 references / Add more references

Citations of this work BETA

Elementary Explicit Types and Polynomial Time Operations.Daria Spescha & Thomas Strahm - 2009 - Mathematical Logic Quarterly 55 (3):245-258.
Definedness.Solomon Feferman - 1995 - Erkenntnis 43 (3):295 - 320.

Add more citations

Similar books and articles


Added to PP index

Total views
221 ( #31,283 of 2,270,987 )

Recent downloads (6 months)
13 ( #64,430 of 2,270,987 )

How can I increase my downloads?


My notes

Sign in to use this feature