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

アルゴリズムの複雑さ（計算の複雑さ、またはコルモゴロフの複雑さ）は、 計算の複雑さの理論とアルゴリズム情報の理論の両方の基本的な考え方であり、形式的な帰納法で重要な役割を果たします。

バイナリ文字列のアルゴリズムの複雑さは、文字列を生成できる最短かつ最も効率的なプログラムとして定義されます。 任意の文字列を生成できるプログラムは無限にありますが、1つのプログラムまたはプログラムのグループが常に最短になります。 特定の文字列を出力する最短のアルゴリズムを見つけるアルゴリズム的な方法はありません。 これは、計算の複雑さの理論の最初の結果の1つです。 それでも、経験に基づいた推測を行うことができます。 この結果（文字列の計算の複雑さ）は、計算可能性に関する証明にとって非常に重要であることがわかりました。

物理オブジェクトまたはプロパティは、原則としてビット列によってほぼ使い果たされていると説明できるため、オブジェクトおよびプロパティもアルゴリズム的に複雑であると言えます。 実際、現実世界のオブジェクトの複雑さを出力としてオブジェクトを生成するプログラムに減らすことは、科学の企業を見る一つの方法です。 私たちの周りの複雑なオブジェクトは、3つの主な生成プロセスから生じる傾向があります。 出現 、 進化 、 インテリジェンス 、それぞれが生成するオブジェクトは、アルゴリズムの複雑さが増す傾向があります。

計算の複雑さは、幅広い種類の数学的および論理的な問題の解決策を計算することの相対的な困難さを判断するために、理論的なコンピューターサイエンスで頻繁に使用される概念です。 400を超える複雑なクラスが存在し、追加のクラスが継続的に発見されています。 有名なP = NPの質問は、これらの複雑度クラスの2つの性質に関するものです。 複雑さのクラスには、計算までの数学で直面するものよりもはるかに難しい問題が含まれます。 計算の複雑さの理論には、解くのにほぼ無限の時間を必要とする多くの考えられる問題があります。

アルゴリズムの複雑さと関連する概念は、1960年代に何十人もの研究者によって開発されました。 Andrey Kolmogorov、Ray Solomonoff、Gregory Chaitinは、60年代後半にアルゴリズム情報理論で重要な貢献をしました。 アルゴリズムの複雑さに密接に関連する最小メッセージ長の原則は、統計的および帰納的推論と機械学習の基礎の多くを提供します。