The Complexity of Songs

From Wikipedia, the free encyclopedia

"The Complexity of Songs" was an article published by Donald Knuth, an example of an in-joke in computer science, namely, in computational complexity theory. The article capitalizes on the tendency of popular songs to evolve from long and content-rich ballads to highly repetitive texts with little or no meaningful content.

With a grain of truth, Knuth writes that "...our ancient ancestors invented the concept of refrain" to reduce the space complexity of songs, which becomes crucial when a large number of songs is to be committed to one's memory. Knuth's Lemma 1 states that if N is the length of a song, then the refrain decreases the song complexity to cN, where c < 1.

Knuth further demonstrates a way of producing songs with O( $\sqrt N$ ) complexity, an approach "...further improved by a Scottish farmer named O. McDonald" (priority disputed).

More ingenious approaches yield songs of complexity O( $log N$ ). Finally, progress during the twentieth century—stimulated by the fact that "the advent of modern drugs has led to demands for still less memory"—leads to the ultimate improvement: Arbitrarily long songs with space complexity O(1), e.g. for a song to be defined by the recurrence relation

$S_0=e, S_k = V_kS_{k-1},\, k\ge 1,$

V k =

'That's the way,'

U

'I like it,'

U

, for all

k > 0

U =

'uh huh, uh huh'

[edit] References

Knuth, D. The Complexity of Songs, SIGACT News, Summer 1977, 17-24.
Knuth, D. The Complexity of Songs, Communications of the ACM, 1984, 27 (4) pp. 345--348.