Degrees of computational complexity

摘要

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.