Polynomial time operations in explicit mathematics

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

Abstract

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

Categories

Keywords

Reprint years

DOI

10.2307/2275547

Other Versions

edition Strahm, Thomas; Cantini, Andrea (2002) "Polynomial Time Operations in Explicit Mathematics". Bulletin of Symbolic Logic 8(4):534-535

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 100,937

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Review: Thomas Strahm, Polynomial Time Operations in Explicit Mathematics ; Andrea Cantini, Feasible Operations and Applicative Theories Based on $\lambda \eta $. [REVIEW]Fernando Ferreira - 2002 - Bulletin of Symbolic Logic 8 (4):534-535.
Feasible Operations and Applicative Theories Based on λη.Andrea Cantini - 2000 - Mathematical Logic Quarterly 46 (3):291-312.
Elementary explicit types and polynomial time operations.Daria Spescha & Thomas Strahm - 2009 - Mathematical Logic Quarterly 55 (3):245-258.
A feasible theory for analysis.Fernando Ferreira - 1994 - Journal of Symbolic Logic 59 (3):1001-1011.
Bounded arithmetic for NC, ALogTIME, L and NL.P. Clote & G. Takeuti - 1992 - Annals of Pure and Applied Logic 56 (1-3):73-117.
Time polynomial in input or output.Yuri Gurevich & Saharon Shelah - 1989 - Journal of Symbolic Logic 54 (3):1083-1088.
An application of category-theoretic semantics to the characterisation of complexity classes using higher-order function algebras.Martin Hofmann - 1997 - Bulletin of Symbolic Logic 3 (4):469-486.
Applicative theories for the polynomial hierarchy of time and its levels.Reinhard Kahle & Isabel Oitavem - 2013 - Annals of Pure and Applied Logic 164 (6):663-675.

Analytics

Added to PP
2009-01-28

Downloads
248 (#106,606)

6 months
8 (#583,676)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Definedness.Solomon Feferman - 1995 - Erkenntnis 43 (3):295 - 320.
Elementary explicit types and polynomial time operations.Daria Spescha & Thomas Strahm - 2009 - Mathematical Logic Quarterly 55 (3):245-258.

Add more citations

References found in this work

Totality in applicative theories.Gerhard Jäger & Thomas Strahm - 1995 - Annals of Pure and Applied Logic 74 (2):105-120.

View all 6 references / Add more references