JavaScriptを有効にしてください

コルモゴロフ複雑性

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

YuWd (Yuiga Wada)
著者
YuWd (Yuiga Wada)
機械学習・競プロ・iOS・Web