歌の複雑さ

「歌の複雑さ」は、コンピュータ科学者ドナルド・クヌースが1977年に発表した学術論文^[1]で、計算複雑性理論に関するジョークとして出版された。この論文は、ポピュラーソングが長くて内容の濃いバラードから、ほとんど意味のない、あるいは全く意味のない非常に反復的な歌詞に退化する傾向があると主張している。[ ^{2]この論文では}、長さN語の歌は、例えばO ( logN )語(歌の「空間複雑性」)あるいはそれ以下の語数しか 覚えずに作れると述べている。

クヌースは、「我々の古代の祖先は、歌の空間的複雑さを減らすためにリフレインの概念を発明した」と書いている。これは、多数の歌を記憶に残すときに重要になる。クヌースの補題1 は、歌の長さをNとすると、リフレインによって歌の複雑さがcNに減少する(係数 c < 1 )と述べている。^[1]

クヌースはさらに、 O（√N）の複雑さを持つ曲を制作する方法を示しており、このアプローチは「O・マクドナルドというスコットランドの農夫によってさらに改良された」^{[1] 。}

さらに独創的なアプローチにより、複雑な曲が生まれ、「壁にビールのボトルがm本」と呼ばれる類の曲も生まれます。 ${\displaystyle O(\log N)}$

最後に、20世紀の進歩は、「現代の薬の出現により、さらに少ないメモリの需要がもたらされた」という事実に刺激され、究極の改善につながりました。空間複雑性を持つ任意の長さの曲が存在する、例えば、${\displaystyle O(1)}$再帰関係^[1]によって定義される曲です。

${\displaystyle S_{0}=\epsilon ,S_{k}=V_{k}S_{k-1},\,k\geq 1,}$

V _k =「その通りだ」、 U「気に入った」、 U、すべてのk ≥ 1について

U =「ああ、そうだね」 「ああ、そうだね」

サンディエゴ州立大学の Kurt Eisemann 教授は、 Communications of the ACM ^[3]への手紙の中で、後者の一見無敵と思われる推定値をさらに改善しています。彼は、実際のアプリケーションでは、ビッグO表記の「隠れた定数」 cの値が、実現可能性と実現不可能性の差を生む上で決定的な要因になる可能性があるという観察から始めています。たとえば、定数値が 10 ⁸⁰であれば、既知のデバイスの容量を超えてしまいます。彼はさらに、任意の曲のテキスト コンテンツを、再帰関係 に基づいて記録できる手法が中世ヨーロッパですでに知られていたことにも注目しています。この場合、ビッグO定数cの値は 2 になります。しかし、別の文化がO (0)の絶対下限を達成していたことが判明しました。Eisemann 教授は次のように述べています。 ${\displaystyle S_{k}=C_{2}S_{k-1}}$${\displaystyle C_{2}={\texttt {'la'}}}$

メイフラワー号の航海者が初めてこの地に降り立ったとき、情報の保存と検索の理論における成果を誇りに思っていたネイティブアメリカンたちは、最初は完全な沈黙でこの見知らぬ人たちを歓迎しました。これは、歌の複雑さにおける彼らの最高の成果、つまりc  = 0 という低い限界が実際に達成可能であることを実証したことを伝えるためでした。

ヨーロッパ人はこの概念を理解する準備ができていなかったと主張されており、首長たちは自分たちの業績を伝える共通の基盤を確立するために、後に再帰関係（ここで、最適ではない複雑さはc = 1 ）で説明されるアプローチを実証しました。^{[2] [3]}${\displaystyle S_{k}=C_{1}S_{k-1}}$${\displaystyle C_{1}={\texttt {'i'}}}$

O (1)の空間計算量という結果はGuy L. Steele, Jr.によっても実装されたが、おそらく Knuth の記事によって異議が唱えられた。^[4] Steele 博士のTELNET Song は指数再帰に基づく全く異なるアルゴリズムを使用しており、TELNET のいくつかの実装のパロディである。^{[5] [6] [7]}

ダラ・チャヴェイは、人間の歌の複雑性分析は、学生に複雑性理論を教えるための有用な教育手段になり得ると示唆した。^[8]

アラン・シャーマン教授 ^[9]の論文「超多対数的 指数関数について」では、クヌースの記事が特殊なクラスの関数の解析に多大な影響を与えたと書かれている。

• 「歌の複雑さ」、ドナルド・E.・クヌース（1984年）。