1
$\begingroup$

It's well-known that the Kolmogorov complexity is uncomputable, essentially because of the halting problem: you can list all programs of length less than one known to generate a given string, but you don't know how long you need to let them run before disqualifying them. But this strikes me as uninteresting, since you might not want to use a program that would take $10^{1000}$ operations to output your string.

It seems that a simple modification gives a complexity which is not only more reasonable (in terms of data compression) but which is computable: count not just space but time. Say, take a model of computation (a programming language and its semantics, together with rules for determining time of execution) and a constant $k>0$. Then the complexity of a(n input-free) program is the size of the program plus $k$ times its execution time, and the complexity of a finite string is the minimum complexity of a program generating it.

This seems too obvious of an idea to be original. Does this have a name? What results are known? (For example, clearly the complexity is in PSPACE, assuming the model allows a fixed string to be printed in time linear in the length of the string.) Are there references?

$\endgroup$

1 Answer 1

1
$\begingroup$

The general idea has been looked at, but there is a difference in a detail: Instead of adding a constant multiple of the time, add the logarithm of the time. This produces Levin complexity, which is related to Levin's "universal search" algorithm.

$\endgroup$
2
  • $\begingroup$ Yes, that seems more natural now that I think about it. $\endgroup$
    – Charles
    Commented Jan 4, 2013 at 21:52
  • $\begingroup$ ...although perhaps with less relevance to compression, in the sense that 1 billion bits is a practical size and 1 billion cycles is a practical time but 2^(1 billion) cycles is a completely impractical time. $\endgroup$
    – Charles
    Commented Jan 4, 2013 at 21:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .