Time polynomial in input or output

&
Journal of Symbolic Logic 54 (3):1083-1088 (1989)
  Copy   BIBTEX

Abstract

We introduce the class PIO of functions computable in time that is polynomial in max{the length of input, the length of output}, observe that there is no notation system for total PIO functions but there are notation systems for partial PIO functions, and give an algebra of partial PIO functions from binary strings to binary strings

Categories

Keywords

Reprint years

DOI

10.2307/2274767

Other Versions

No versions found

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

Predicatively computable functions on sets.Toshiyasu Arai - 2015 - Archive for Mathematical Logic 54 (3-4):471-485.
Polynomial time operations in explicit mathematics.Thomas Strahm - 1997 - Journal of Symbolic Logic 62 (2):575-594.
A Simple Observation Regarding Iterations Of Finite-valued Polynomial-time Functions.Jerzy Mycka - 2009 - Reports on Mathematical Logic:19-29.
Generalization of Shapiro’s theorem to higher arities and noninjective notations.Dariusz Kalociński & Michał Wrocławski - 2022 - Archive for Mathematical Logic 62 (1):257-288.
Admissible closures of polynomial time computable arithmetic.Dieter Probst & Thomas Strahm - 2011 - Archive for Mathematical Logic 50 (5):643-660.
Higher type recursion, ramification and polynomial time.Stephen J. Bellantoni, Karl-Heinz Niggl & Helmut Schwichtenberg - 2000 - Annals of Pure and Applied Logic 104 (1-3):17-30.
On Nondeterminism, Enumeration Reducibility and Polynomial Bounds.Kate Copestake - 1997 - Mathematical Logic Quarterly 43 (3):287-310.
Bounded arithmetic for NC, ALogTIME, L and NL.P. Clote & G. Takeuti - 1992 - Annals of Pure and Applied Logic 56 (1-3):73-117.
A set theory with support for partial functions.William M. Farmer & Joshua D. Guttman - 2000 - Studia Logica 66 (1):59-78.
Universal functions in partial structures.Maurizio Negri - 1992 - Mathematical Logic Quarterly 38 (1):253-268.

Analytics

Added to PP
2009-01-28

Downloads
35 (#646,056)

6 months
11 (#345,260)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references