FC2ブログ

コルモゴロフ複雑性

先日ランダム性について云々したことがあって、
いや日付とかは忘れて、しかも探す気もない。

んで、どこぞの先輩が書いたようなそうでないような
ページを思い出していて
「雑な定義」をそのまま定義として理解してた。迂闊。

同値な定義がいくつかあるらしいけど
やっぱりこのコルモゴロフ複雑性の定義は計算機数学的でしっくりくるね。

ところがや、
「文字列 x がc圧縮不可能ならばその部分文字列もc圧縮不可能」っていう
簡単な事実を、まぁこれはそれほど証明は面倒臭くないと思うけど
結局はアルゴリズムの存在性とか非存在性に帰着しなきゃいけないのは
どうしても話がややこしくなる。

学問として発展するのに、P=NP?みたいに
接近不可能な問題が早い段階で現れてくるでしょ。きっと。
どうにかならんかね。
関連記事

コメントの投稿

非公開コメント

a8
最近の記事
月別アーカイブ
ブログ内検索
グリムス
フリーエリア
リンク
RSSフィード