Polynomial Time Operations in Explicit Mathematics
Strahm, Thomas
J. Symbolic Logic, Tome 62 (1997) no. 1, p. 575-594 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
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 $\mathbb{W} = \{0, 1\}^\ast$ are exactly the polynomial time computable functions. Our treatment of PTO is proof-theoretic and very much in the spirit of reductive proof theory.
Publié le : 1997-06-14
Classification:  
@article{1183745243,
     author = {Strahm, Thomas},
     title = {Polynomial Time Operations in Explicit Mathematics},
     journal = {J. Symbolic Logic},
     volume = {62},
     number = {1},
     year = {1997},
     pages = { 575-594},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183745243}
}

Strahm, Thomas. Polynomial Time Operations in Explicit Mathematics. J. Symbolic Logic, Tome 62 (1997) no. 1, pp.  575-594. http://gdmltest.u-ga.fr/item/1183745243/