アルゴリズムの複雑さとは何ですか？

アルゴリズムの複雑さ（計算の複雑さ、またはコルモゴロフの複雑さ）は、計算複雑さ理論およびアルゴリズム情報理論の両方の基本的なアイデアであり、正式な誘導において重要な役割を果たします。binaryバイナリ文字列のアルゴリズムの複雑さは、文字列を生成できる最短かつ最も効率的なプログラムとして定義されます。特定の文字列を生成できるプログラムは無限にありますが、1つのプログラムまたはプログラムグループが常に最短になります。特定の文字列を出力する最短アルゴリズムを見つけるアルゴリズムの方法はありません。これは、計算複雑度理論の最初の結果の1つです。それでも、私たちは教育を受けた推測をすることができます。この結果（文字列の計算の複雑さ）は、計算可能性に関連する証明にとって非常に重要であることが判明しました。アルゴリズムの複雑さもあると言えます。実際、オブジェクトを出力として生成するプログラムに現実世界のオブジェクトの複雑さを減らすことは、科学の企業を見る1つの方法です。私たちの周りの複雑なオブジェクトは、3つの主要な生成プロセスから来る傾向があります。

、出現

、

進化

、および知能、それぞれが生成するオブジェクトは、より大きなアルゴリズムの複雑さに向かう傾向があります。数学的および論理的な問題の。400を超える複雑なクラスが存在し、追加のクラスが継続的に発見されています。有名なp 'np質問は、これらの複雑さの2つのクラスの性質に関するものです。複雑なクラスには、数学で計算まで直面する可能性のあるものよりもはるかに困難な問題が含まれます。計算の複雑さ理論には多くの想像上の問題があり、それは解決にほぼ無限の時間を必要とします。Andrey Kolmogorov、Ray Solomonoff、Gregory Chaitinは、60年代後半にアルゴリズム情報理論で重要な貢献をしました。アルゴリズムの複雑さに密接に関連する最小メッセージ長の原理は、統計的および誘導的な推論と機械学習の基礎の多くを提供します。