On computational reducibility

摘要

A function is said to be computationally reducible to another if it requires less space(or a smaller amount of some other resource) to compute. When the recursive functions are ordered according to this reducibility several interesting facts emerge. The classes formed with functions that have “best algorithms” correspond to the complexity classes named by tape-complexity functions. In addition, several results concerning the structure of complexity classes and density are presented.