Name
Abstract | ||
|---|---|---|
We focus on notions of resource-bounded complexity for infinite binary sequences, and compare both, a definition based on Kobayashi's concept 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 sequences 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 Kobayashi and Loveland complexity concepts are equivalent under a small constant factor. This also works under time bounds if instead of bounding functions that are recursive, those that are computed within the allowed time are considered. (C) 1997 Elsevier Science B.V. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1016/S0020-0190(97)00070-7 | Inf. Process. Lett. |
Keywords | Field | DocType |
uniform complexity,polynomial time,turing machine,compressibility,computational complexity,binary sequence | Compressibility,Discrete mathematics,Monotonic function,Combinatorics,Kolmogorov complexity,Polynomial,Time complexity,Recursion,Mathematics,Computational complexity theory,Bounded function | Journal |
Volume | Issue | ISSN |
62 | 5 | 0020-0190 |
Citations | PageRank | References |
1 | 0.37 | 5 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Montserrat Hermo | 1 | 55 | 10.77 |