COMPRESSIBILITY AND UNIFORM COMPLEXITY

We focus on notions of resource-bounded complexity for infinite binary sequences, and compare both, a definition based on Kobayashi's concep t of compressibility, and the uniform approach studied by Loveland. It is known that for constant bounds on the complexity these definitions exactly coincide, and characterize the polynomial-time computable seq uences when the running time is bounded by a polynomial, together with the recursive sequences when there is no time bound. We show here how for complexity functions that are monotonic, and recursive, the Kobay ashi and Loveland complexity concepts are equivalent under a small con stant factor. This also works under time bounds if instead of bounding functions that are recursive, those that are computed within the allo wed time are considered. (C) 1997 Elsevier Science B.V.