Polynomial time operations in explicit mathematics

Strahm, Thomas (1997). Polynomial time operations in explicit mathematics. The journal of symbolic logic, 62(2), pp. 575-594. Cambridge University Press 10.2307/2275547

[img]
Preview
Text
S0022481200016364.pdf - Published Version
Available under License Publisher holds Copyright.

Download (1MB) | Preview

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.

Item Type:

Journal Article (Original Article)

Division/Institute:

08 Faculty of Science > Institute of Computer Science (INF)

UniBE Contributor:

Strahm, Thomas Adrian

Subjects:

000 Computer science, knowledge & systems
500 Science > 510 Mathematics

ISSN:

0022-4812

Publisher:

Cambridge University Press

Language:

English

Submitter:

Marceline Brodmann

Date Deposited:

28 Jul 2020 11:03

Last Modified:

05 Dec 2022 15:13

Publisher DOI:

10.2307/2275547

BORIS DOI:

10.7892/boris.115326

URI:

https://boris.unibe.ch/id/eprint/115326

Actions (login required)

Edit item Edit item
Provide Feedback