
We consider a measure Φ of computational complexity. The measure Φ determinesa binary relation on the recursive functions; F is no harder to compute than G iff for every index g of G there is an index f of F such that for nearly all x, the difficulty of f at x (as measured by Φ) is no more than the difficulty of g at x. The corresponding symmetric relation is an equivalence relation, and the set of equivalence classes (the degrees of complexity) is partially ordered. In this paper we give a simple proof of a result of McCreight: An arbitrary countable partial ordering can be embedded in this ordering of degrees of complexity.
Computational Theory and Mathematics, Computer Networks and Communications, Analysis of algorithms and problem complexity, Applied Mathematics, Theoretical Computer Science
Computational Theory and Mathematics, Computer Networks and Communications, Analysis of algorithms and problem complexity, Applied Mathematics, Theoretical Computer Science
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 9 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
