We consider a measure ~b of computational complexity. The measure 9 determines a 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 off such that for nearly all x, the difficulty off 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.
- All recursive functions are computable, but some are more computable than others. To make this idea meaningful, an axiomatic approach to computational complexity has been utilized by Rabin [8], Blum [2], and others. (Further references may be found in .) Let q~1(x) measure the "difficulty" of applying the computational procedure with index f to the input x. (Formally, 9 is any recursive partial function satisfying some modest axioms to be stated shortly.) DEFINITION. F is no harder to compute than G (written: F -~ G) if (V indexg of G)(3 indexfofF)(W ~ x) @~(x) <~ @g(x). (Cf. [1, p. 267].) Here "V * x" means "for all but finitely many values of x," or more briefly, "for nearly all x." The corresponding equivalence relation (F _= G if F ~ G and G ~, F) partitions the class of recursive functions into equivalence classes, the degrees of (computational) complexity. These degrees are partially ordered by the relation (which is well defined on equivalence classes). This partial ordering turns out to be very wild indeed. In this paper we will give a simple proof that any countable partial ordering can be embedded in the ordering of the degrees of complexity. This theorem follows from a result of McCreight announced in and proved in his dissertation . (See 5.2 and 5.3 of [6].) But we believe the present proof to be conceptually simpler.