複雑性
複雑性の定義は、「システム」の概念と結び付けられていることが多い。システムとは部品や要素の集合であり、その部品や要素には互いに関係があり、システム外の要素とは関係の質が異なる。多くの定義は、システム内の多数の要素の状態とその要素間の関係の様々な形態を表現するのが複雑性という言葉だと仮定する傾向がある。同時に、何が複雑で何が単純なのかは相対的であり、その場その場で変化する。
定義によっては、システムの特徴が指定されたとき、与えられたシステム状態に遭遇する確率の問題に焦点を合わせている。ウォーレン・ウィーバーは、システムの部品毎の属性が与えられたとき、システム全体の属性を予測する困難さの度合いを複雑性であるとした。ウィーバーの観点では、複雑性は組織化されていない複雑性 (disorganized complexity) と組織化された複雑性 (organized complexity) という2つの形態に分類される。ウィーバーの論文はその後の複雑性の研究に影響を与えている。
システム、複数の要素、複数の関係の型、状態空間といった概念を具体化するアプローチは、定義されたシステム内の識別可能な関係の型(およびそれらの関連する状態空間)の数を複雑性とすることを暗に示していると言えるかもしれない。
定義によっては複雑な現象やモデルや数式を説明するアルゴリズムとの関係が深いものもある。
マサチューセッツ工科大学のセス・ロイドは、複雑性の定義を32種類集めてプレゼンテーションしたことがあるという。
科学のいくつかの分野では、「複雑性」は次のような意味を持つ。
計算複雑性理論では、アルゴリズムの実行に必要となる計算資源の量を研究する。「複雑性」を「計算量」とも呼び、具体的問題を最適なアルゴリズムを使って解くのに要するステップ数をその問題の入力の長さ(例えばビット数)の関数として表したものを時間計算量と呼ぶ。また、具体的問題を最適なアルゴリズムを使って解くのに要するメモリ量(例えば、テープ上のセル数)をその問題の入力の長さ(例えばビット数)の関数として表したものを空間計算量と呼ぶ。これによって計算問題を複雑性クラス(P、NPなど)に分類する。マヌエル・ブラムは計算複雑性理論の公理的手法を開発した。それによると、時間計算量や空間計算量といった具体的な複雑性尺度の多くの特性を公理的に定義された尺度の特性から演繹できる。
アルゴリズム情報理論において、文字列の「コルモゴロフ複雑性」とは出力がその文字列に一致するプログラムの長さの最小値である。ブラムの公理に基づいたコルモゴロフ複雑性の公理的アプローチは、Mark Burgin が論文で提唱した。公理的アプローチは他の手法も包含している。そして、公理的に定義された一般化されたコルモゴロフ複雑性の特殊ケースとして様々な種類のコルモゴロフ複雑性を扱うことができる。様々な測度について例えば基本不変定理のような似たような定理を個別に証明する代わりに、この公理的設定で証明した1つの定理から個別の証明を演繹することができる。