Time polynomial in input or output

1 September 1989

journal article
Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic

Vol. 54 (3) , 1083-1088
https://doi.org/10.2307/2274767

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.

Keywords

POLYNOMIAL
INPUT
OUTPUT
PIO FUNCTIONS
NOTATION
PARTIAL
STRINGS
BINARY

This publication has 2 references indexed in Scilit:

Nearly linear time
Published by Springer Nature ,1989
Binding performance at language design time
Published by Association for Computing Machinery (ACM) ,1987