Publisher： Cambridge University Press
E-ISSN： 1943-5886|54|3|1083-1088
ISSN： 0022-4812
Source： The Journal of Symbolic Logic, Vol.54, Iss.3, 1989-09, pp. : 1083-1088
Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.
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.
Related content
Input-output models and cost inflation
Bulletin of the Australian Mathematical Society, Vol. 13, Iss. 3, 1975-12 ,pp. :
Access to resources
Recommend
Parallelizing Time with Polynomial Circuits
Theory of Computing Systems, Vol. 48, Iss. 1, 2011-01 ,pp. :
Circle Packings of Maps in Polynomial Time
By Mohar B.
European Journal of Combinatorics, Vol. 18, Iss. 7, 1997-10 ,pp. :
Polynomial time operations in explicit mathematics
The Journal of Symbolic Logic, Vol. 62, Iss. 2, 1997-06 ,pp. :