Time Polynomial in Input or Output

Gurevich, Yuri; Shelah, Saharon

J. Symbolic Logic, Tome 54 (1989) no. 1, p. 1083-1088 / Harvested from Project Euclid

Résumé

We introduce the class PIO of functions computable in time that is polynomial in $\max\{\text{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.

Publié le : 1989-09-14
Classification:

@article{1183743042,
     author = {Gurevich, Yuri and Shelah, Saharon},
     title = {Time Polynomial in Input or Output},
     journal = {J. Symbolic Logic},
     volume = {54},
     number = {1},
     year = {1989},
     pages = { 1083-1088},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183743042}
}

Gurevich, Yuri; Shelah, Saharon. Time Polynomial in Input or Output. J. Symbolic Logic, Tome 54 (1989) no. 1, pp.  1083-1088. http://gdmltest.u-ga.fr/item/1183743042/