Weak complexity measures
Ivan M. Havel · ACM SIGACT News · 1971
The well-known abstract approach to the theory of computational complexity is based on two axioms (Ax. 1 and 2 below) for complexity measures introduced by Blum [I].Blum's axioms are generally considered to be the widest formalization of the intuitive concept of computational complexity that still yields interesting results.However, it appears that Blum's axioms can be further weakened without loss of their mathematical power, and, moreover, in some respect with a benefit in their relevance to corresponding intuitive concepts.Let ~n (~n) be the set of all partial recursive (recursive) functions of n variables.Let {~i}i¢ N be a fixed but arbitrary enumeration of ~I' acceptable in the sense of [3] (p. 41).For ~ ~ ~I' x ~ N, t(x) + will mean " ~ converges (is defined) for x" and qb(x) + will mean " ~ diverges in x".Consider a sequence ~ = { ~i }iEN of functions of one variable associated with { q~i }iEN " Such a sequence is called a strong measure of complexity (SM) iff the following axioms are satisfied.