自明な上限

ウィキペディア小見出し辞書

自明な上限

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/19 04:09 UTC 版)

「コルモゴロフ複雑性」の記事における「自明な上限」の解説

前述の例で示されたように明示的に文字列 x をプログラムに含めることができるので、すべての x に対してそのコルモゴロフ複雑性 Ku(x) は x 自体の長さ |x| を定数分以上越えることはない。 すなわち、 定理： 任意の u に対して、ある定数 c が存在して、任意の x に対して、 K u ( x ) ≤ | x | + c が成り立つ。