Published online by Cambridge University Press: 12 March 2014
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.