|
Title:
|
Compressibility of infinite binary sequences
|
|
Author:
|
Balcázar Navarro, José Luis; Gavaldà Mestre, Ricard; Hermo Huguet, Montserrat
|
|
Other authors:
|
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació |
|
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. |
|
Subject(s):
|
-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica
-Kolmogorov complexity
-Infinite binary sequences |
|
Rights:
|
|
|
Document type:
|
Article - Published version
Report |
|
Share:
|
|
