Return to Answer

After making the above comment I did a quick Google search and found a paper entitled "Kolmogorov Complexity and Computational Complexity" by Lance Fortnow. The paper is about resource-bounded variants of Kolmogorov complexity. After giving the standard definition and some consequences he writes the following.

Of course this definition of Kolmogorov complexity makes any complexity theorist cringe: what good is a small program [for] $x$ if it takes the life of the universe to produce $x$?

Perhaps he could give you more precise pointers to the literature.

[Edit] - Your main observation has been made before, by Henry Cohn, on MathOverflow. See the last paragraph of his answer here.

After making the above comment I did a quick Google search and found a paper entitled "Kolmogorov Complexity and Computational Complexity" by Lance Fortnow. The paper is about resource-bounded variants of Kolmogorov complexity. After giving the standard definition and some consequences he writes the following.

Of course this definition of Kolmogorov complexity makes any complexity theorist cringe: what good is a small program [for] $x$ if it takes the life of the universe to produce $x$?

Perhaps he could give you more precise pointers to the literature.

[Edit] - Your main observation has been made before, by Henry Cohn, on MathOverflow. See the last paragraph of his answer here.

After making the above comment I did a quick Google search and found a paper entitled "Kolmogorov Complexity and Computational Complexity" by Lance Fortnow. The paper is about resource-bounded variants of Kolmogorov complexity. After giving the standard definition and some consequences he writes the following.

Of course this definition of Kolmogorov complexity makes any complexity theorist cringe: what good is a small program [for] $x$ if it takes the life of the universe to produce $x$?

Perhaps he could give you more precise pointers to the literature.

After making the above comment I did a quick Google search and found a paper entitled "Kolmogorov Complexity and Computational Complexity" by Lance Fortnow. The paper is about resource-bounded variants of Kolmogorov complexity. After giving the standard definition and some consequences he writes the following.

Of course this definition of Kolmogorov complexity makes any complexity theorist cringe: what good is a small program [for] $x$ if it takes the life of the universe to produce $x$?

Perhaps he could give you more precise pointers to the literature.

[Edit] - Your main observation has been made before, by Henry Cohn, on MathOverflow. See the last paragraph of his answer here.

A Google search finds the paper "Kolmogorov Complexity and Computational Complexity" by Lance Fortnow. The paper is about resource-bounded variants of Kolmogorov complexity. After giving the usual definition and some consequences he writes the following.

Of course this definition of Kolmogorov complexity makes any complexity theorist cringe: what good is a small program [for] $x$ if it takes the life of the universe to produce $x$?

Perhaps he could give you more precise pointers to the literature.

After making the above comment I did a quick Google search and found a paper entitled "Kolmogorov Complexity and Computational Complexity" by Lance Fortnow. The paper is about resource-bounded variants of Kolmogorov complexity. After giving the standard definition and some consequences he writes the following.

Of course this definition of Kolmogorov complexity makes any complexity theorist cringe: what good is a small program [for] $x$ if it takes the life of the universe to produce $x$?

Perhaps he could give you more precise pointers to the literature.