- 文字列の複雑性を記述することができる
- 例えば
- A: 010101010101010101010101010101010101010101010101010101010101
- B: 110010000110000111011110111011001111101001000010010101111001
- ↑ どっちが複雑と言えるか? → B
- Bが複雑だということをどう表現するか.
- 例えば, 人間であれば「説明が簡単かどうか」を指標にすることができる
- これをコンピュータに落とし込めば…
- [* 出力 $x$ を出力できるプログラムのうち, 最も文字数が短いプログラムの文字数]
- これをコルモゴロフ複雑性と呼ぶ.
- [* 出力 $x$ を出力できるプログラムのうち, 最も文字数が短いプログラムの文字数]
JavaScriptを有効にしてください
コルモゴロフ複雑性
· ☕ 1 min read