Time polynomial in input or output
Yuri G. Gurevich, Saharon Shelah · Journal of Symbolic Logic · 1989
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.