Abstract:
|
It is known that infinite binary sequences of constant
Kolmogorov complexity are exactly the recursive ones.
Such a kind of statement no longer holds in the presence of resource bounds.
Contrary to what intuition might suggest, there are sequences of
constant, polynomial-time bounded Kolmogorov complexity that are
not polynomial-time computable. This motivates the study of
several resource-bounded variants in search for a characterization,
similar in spirit, of the polynomial-time computable sequences.
We propose some definitions, based on Kobayashi's notion of
compressibility, and compare them to both the standard resource-bounded
Kolmogorov complexity of infinite strings, and the uniform complexity.
Some nontrivial coincidences and disagreements are proved.
The resource-unbounded case is also considered. |