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
$\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$
  • $\begingroup$ Yes, that seems more natural now that I think about it. $\endgroup$ – Charles Jan 4 '13 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 Jan 4 '13 at 21:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.