複雑

複雑性とは、構成要素が複数の方法で相互作用し、局所的なルールに従うシステムまたはモデルの挙動を特徴づけるものであり、非線形性、ランダム性、集団的ダイナミクス、階層性、および創発につながる。^{[ 1 ] [ 2 ]}

この用語は一般的に、多くの部分から構成され、それらの部分が様々な形で相互作用し、最終的に部分の総和よりも大きな高次の創発効果を生み出すものを特徴づけるために用いられる。様々なスケールにおけるこうした複雑な相互作用の研究が、複雑系理論の主な目的である。

複雑さの直感的な基準は次のように定式化できる。より多くの部分を区別でき、それらの間のつながりが多いほど、システムはより複雑になる。^{[ 3 ]}

2010年現在科学では複雑性を特徴づけるための様々なアプローチが用いられてきました。Zayedら^{[ 4 ]}は これらの多くを反映しています。Neil Johnson は、「科学者の間でも複雑性の定義は一つではなく、科学的概念は伝統的に具体的な例を用いて伝えられてきた」と述べています。最終的に Johnson は「複雑性科学」の定義を「相互作用するオブジェクトの集合から生じる現象の研究」としています。^{[ 5 ]}

複雑性の定義はしばしば「システム」という概念に依存する。システムとは、相互に関係を持ち、その関係性の外にある他の要素との関係性とは区別される、構成要素または要素の集合である。多くの定義は、複雑性とはシステム内の多数の要素と、それらの要素間の多数の関係性の状態を表すと仮定または想定する傾向がある。しかし、何が複雑で何が単純かは相対的なものであり、時間とともに変化する。

ウォーレン・ウィーバーは1948年に、複雑性の2つの形態、すなわち無秩序な複雑性と組織化された複雑性を提唱した。^{[ 6 ]} 「無秩序な複雑性」の現象は確率論と統計力学を用いて扱われる一方、「組織化された複雑性」は、そのようなアプローチでは対処できない現象を扱い、「有機的な全体として相互に関連する相当数の要因を同時に扱う」という課題に直面する。^{[ 6 ]}ウィーバーの1948年の論文は、その後の複雑性に関する考え方に影響を与えた。^{[ 7 ]}

システム、複数の要素、複数の関係体制、状態空間といった概念を取り入れたアプローチは、定義されたシステムにおける区別可能な関係体制（およびそれに関連する状態空間）の数から複雑さが生じることを示唆していると要約できるだろう。

後述するように、いくつかの定義は、複雑な現象、モデル、または数式を表現するためのアルゴリズム的基礎に関連するものです。

複雑性の問題に取り組む上での課題の一つは、ランダムな集合に存在する関係性の多様性と、制約（本来独立した要素間の相関関係に関連するもの）によって要素間の独立性からの変動が同時に減少し、より均一な、あるいは相関関係のある関係性や相互作用の区別可能な状態が作り出されるシステムにおける、要素間の関係性の数は多い場合もあるが、それよりは少ないという、直感的な概念的区別を形式化することであった。

ウィーバーはこの問題を少なくとも予備的な方法で認識し、対処しました。「無秩序な複雑性」と「組織化された複雑性」を区別したのです^{[ 8 ]}：複雑な相互作用パターンは、複数のエンティティの局所的な相互作用によって発生する場合もあれば、一貫性のある全体を形成し、ある程度の中心的な制御と調整を持つ要素間の相互作用によって発生する場合もあります。どちらのタイプの複雑性もフィードバックループを伴う可能性がありますが、これらのメカニズムは性質が異なります。

一般的に、特定のシステムにおける複雑性の起源を説明するために援用できる規則が存在する。

複雑で秩序のない状態の原因は、対象となるシステムに含まれる部品の数が多いことと、システム内の要素間の相関関係が欠如していることにある。

自己組織化する生命システムの場合、有用な組織化された複雑性は、環境によって、異なる生殖能力、あるいは少なくとも無生物や組織化されていない複雑生物よりも優れているという理由で生存するように選択された、有益な突然変異生物から生じます。例えば、ロバート・ウラノヴィッチによる生態系の扱いを参照してください。^{[ 13 ]}興味深いことに、この生物の複雑性と遺伝子の平均長の間には強い相関関係が見られます。^{[ 14 ]}

オブジェクトやシステムの複雑さは相対的な性質です。例えば、多くの関数（問題）において、計算時間などの計算複雑性は、シングルテープのチューリングマシンを使用する場合よりもマルチテープのチューリングマシンを使用する場合の方が小さくなります。ランダムアクセスマシンは時間計算量をさらに低減させることができ（Greenlaw and Hoover 1998: 226）、帰納的チューリングマシンは関数、言語、または集合の複雑性クラスさえも低減させることができます（Burgin 2005）。これは、活動ツールが複雑性の重要な要素となり得ることを示しています。

いくつかの科学分野において、「複雑性」には明確な意味がある。

• 計算複雑性理論では、アルゴリズムの実行に必要なリソースの量が研究されます。最も一般的な計算複雑性の種類は、最も効率的なアルゴリズムを使用して、入力サイズ（通常はビット単位）の関数として問題のインスタンスを解決するのに必要なステップ数に等しい問題の時間複雑性と、最も効率的なアルゴリズムを使用して、入力サイズ（通常はビット単位）の関数として問題のインスタンスを解決するのに必要なアルゴリズムが使用するメモリのボリューム（テープのセルなど）に等しい問題の空間複雑性です。これにより、計算問題を複雑性クラス（P、NPなど）で分類できます。計算複雑性に対する公理的アプローチは、マヌエル・ブルムによって開発されました。これにより、公理的に定義された尺度の特性から、時間複雑性や空間複雑性などの具体的な計算複雑性尺度の多くの特性を推論できます。
• アルゴリズム情報理論では、文字列のコルモゴロフ複雑度（記述的複雑度、アルゴリズム的複雑度、またはアルゴリズム的エントロピーとも呼ばれる）は、その文字列を出力する最短のバイナリプログラムの長さです。最小メッセージ長は、このアプローチの実用的な応用です。コルモゴロフ複雑度には、均一複雑度、接頭辞複雑度、単調複雑度、時間制限付きコルモゴロフ複雑度、空間制限付きコルモゴロフ複雑度など、さまざまな種類があります。ブルム公理（ブルム 1967）に基づくコルモゴロフ複雑度への公理的アプローチは、アンドレイ・コルモゴロフが発表した論文でマーク・バーギンによって導入されました。^{[ 15 ]}この公理的アプローチは、コルモゴロフ複雑度への他のアプローチを包含しています。さまざまな種類のコルモゴロフ複雑度を、公理的に定義された一般化コルモゴロフ複雑度の特殊なケースとして扱うことができます。基本的な不変性定理など、類似の定理を個々の尺度ごとに証明する代わりに、公理的設定で証明された対応する定理から、そのような結果すべてを容易に導き出すことができます。これは、数学における公理的アプローチの一般的な利点です。コルモゴロフ複雑性に対する公理的アプローチは、書籍（Burgin 2005）でさらに発展し、ソフトウェアメトリクス（Burgin and Debnath, 2003; Debnath and Burgin, 2003）に適用されました。
• 情報理論において、情報変動複雑性とは、情報エントロピーに関する情報の変動を指します。これは、動的システムにおける秩序と混沌の優位性の変動から導き出され、様々な分野で複雑性の尺度として用いられてきました。
• 情報処理において、複雑性とは、対象物によって伝達され、観察者によって検出される特性の総数を表す尺度である。このような特性の集合は、しばしば状態と呼ばれる。
• 物理システムにおいて、複雑性とはシステムの状態ベクトルの確率を表す尺度である。これはエントロピーと混同してはならない。複雑性とは、統計力学におけるエントロピーの概念のように、2つの異なる状態を同一視したり、等しいとみなしたりすることのない、全く異なる数学的尺度である。
• 動的システムでは、統計的複雑性は、データセット（シーケンス）に含まれるパターン（構成）を統計的に再現できる最小プログラムのサイズを測定します。^{[ 16 ] [ 17 ]}アルゴリズム的複雑性はオブジェクトの決定論的記述（個々のシーケンスの情報量を測定する）を意味しますが、統計的複雑性は、予測複雑性と同様に、^{[ 18 ]}統計的記述を意味し、特定のソースによって生成されたシーケンスのアンサンブルを指します。形式的には、統計的複雑性は、類似した確率的未来を共有するすべての履歴の集合を含む最小モデルを再構築し、このモデル内の状態の確率分布のエントロピーを測定します。これは、システムの内部ダイナミクスのみに基づく計算可能で観測者に依存しない尺度であり、創発と自己組織化の研究で使用されています。^{[ 19 ]}
• 数学において、クローン・ローズ複雑性は有限半群やオートマトンの研究における重要なトピックである。
• ネットワーク理論では、複雑性はシステムの構成要素間の接続の豊富さの産物であり、^{[ 20 ]}特定の尺度の非常に不均等な分布によって定義されます（一部の要素は高度に接続され、一部は非常に少ない、複雑ネットワークを参照）。
• ソフトウェア工学において、プログラミング複雑度とは、ソフトウェアの様々な要素間の相互作用を測る尺度です。これは、ソフトウェアの設計を測る尺度であるという点で、前述の計算複雑度とは異なります。ハルステッド複雑度、循環的複雑度、時間複雑度、パラメータ化複雑度は、密接に関連する概念です。
• モデル理論において、Uランクは安定理論の文脈における完全型の複雑さを測る尺度である。
• バイオインフォマティクスにおいて、言語配列の複雑性とは、遺伝子配列における遺伝子テキストの語彙の豊富さを測る指標である。
• 統計的学習理論において、ヴァプニック・チェルヴォネンキス次元は、集合のクラスの規模（容量、複雑さ、表現力、豊かさ、柔軟性）を測る尺度である。
• 計算学習理論において、ラデマッハー複雑度とは、確率分布に関して、ある集合のクラスの豊富さを測る尺度である。
• 社会学において、社会複雑性とは、社会分析に用いられる概念的枠組みである。
• 組み合わせゲーム理論において、ゲームの複雑さを測る尺度は、様々なゲームシナリオにおけるゲームの状態、起こりうる結果、および必要な計算を理解することを含む。
• バイナリ数では、抽象的複雑性定義 (ACD) は、複雑性をバイナリ構造の複雑性として形式化し、式 C = N² / n で表します。ここで、N は検出可能な規則性 (コントラスト) の数、n は基本要素 (0 と 1) の数です。これらの規則性は、共通点と相違点の相互作用から生じる緊張であるコントラスト、および構造情報 (シャノンの通信情報とは対照的) と同一視されます。この式には、次の 2 つの要素が組み込まれています。• 情報圧縮/密度を表す N/n 比、およびより長い構造を圧縮することの難しさを考慮するために導入された規則性の数 N。この定義は、システムがバイナリ形式で表現できる場所であればどこでも、例えば音楽など、類推的にも直接的にも適用されます。古典的な構造的複雑性定義との違い: 従来の定義は、要素と関係の数に焦点を当て、これらの関係の性質を指定しません。ACD では、関係は、定義されたダイナミクスを持つシステム要素の共通点と相違点の相互作用から生じる緊張 (コントラスト) として明示的に定義されます。これにより、定義は構成的かつ操作的になり、複雑さの形式的な計算が可能になります。複雑さの直感的な基準: 複雑さは、識別可能な要素の数とそれらの間の接続の数です。コントラストに関連して: 区別する特徴は識別可能な要素に対応し、共通の特徴はそれらの要素間の接続に対応します。そのような特徴が多く存在し、それらの相互作用が強いほど、コントラストは大きくなり、したがって複雑さも高くなります。^{[ 21 ] [ 22 ]}

他の分野では、複雑性に関するより曖昧な概念が導入されている。

• 複雑適応システムは、以下の属性の一部または全部を備えています。^{[ 5 ]}
  • システム内の部品の数（および部品の種類）と部品間の関係の数は、決して些細なものではありません。ただし、「些細な」と「些細でない」を区別する一般的な規則はありません。
  • システムはメモリを備えているか、フィードバック機能を備えている。
  • システムは、その履歴やフィードバックに基づいて自己適応することができる。
  • システムとその環境との関係は、自明ではない、あるいは非線形である。
  • システムは、環境の影響を受けることもあれば、環境に適応することもある。
  • このシステムは初期条件に非常に敏感である。
• ピーク複雑性とは、人間社会は社会経済的な複雑性を加えることで問題に対処していくが、その過程は限界収益逓減の法則に従うという概念である。

複雑性は常に私たちの環境の一部であり、そのため多くの科学分野が複雑系や複雑現象を扱ってきました。ある観点から言えば、何らかの形で複雑性を持つもの、つまりランダムではない変化を示すものは、探求の深淵に見出される恩恵を考えると、最も関心に値するものと言えるでしょう。

「複雑」という用語は、「難解」という用語と混同されることが多い。今日のシステムでは、これは無数の接続された「縦割り」と効果的な「統合」ソリューションの違いである。^{[ 23 ]}つまり、「複雑」は「独立」の反対であり、「難解」は「単純」の反対である。

これにより、いくつかの分野では複雑性の具体的な定義が考案されましたが、アリ塚、人間の脳、社会システムなど、複雑性そのものを研究するために、さまざまな分野からの観察を再編成する最近の動きがあります。^{[ 24 ]}そのような学際的な分野のグループの一つが関係秩序理論です。

計算複雑性理論とは、問題の複雑性、つまり問題を解決する難しさを研究する学問です。問題は、アルゴリズム（通常はコンピュータプログラム）が問題を解決するのにかかる時間に基づいて、複雑性クラスに分類できます。問題は、解決が難しい場合もあれば、簡単な場合もあります。例えば、難しい問題の中には、問題のサイズに対して指数関数的に時間がかかるアルゴリズムを必要とするものがあります。巡回セールスマン問題を例にとってみましょう。この問題は、ビッグオー記法で表すと、時間で解くことができます。${\displaystyle O(n^{2}2^{n})}$（ここでnは訪問するネットワークのサイズ、つまり巡回セールスマンが必ず一度ずつ訪問しなければならない都市の数です。）都市のネットワークのサイズが大きくなるにつれて、ルートを見つけるのに必要な時間は指数関数的に（それ以上に）増加します。

原理的には計算で解決可能な問題であっても、実際にはそれほど単純ではない場合があります。こうした問題には、膨大な時間や膨大な量のメモリが必要になることがあります。計算複雑性は、さまざまな側面からアプローチできます。計算複雑性は、問題解決に使用される時間、メモリ、その他のリソースに基づいて調査できます。時間と空間は、複雑性の問題が分析される際に最も重要でよく考慮される要素の2つです。

原理的には解決可能であるにもかかわらず、解決に膨大な時間や空間を要するため、実際に解決を試みることが現実的ではない問題が存在する。このような問題は「解決困難な問題」と呼ばれる。

複雑性には、階層的複雑性と呼ばれる別の形態があります。これは、これまで議論してきた水平的複雑性と呼ばれる形態とは直交するものです。

複雑性の概念は、宇宙論、ビッグヒストリー、文化進化の研究において、より詳細な分析と定量化の進展とともに、ますます広く用いられるようになっている。

• Chapouthier, Georges (2024). "モザイク状の複雑性：生物から倫理へ". EPJ Web of Conferences . 300 : 01006. Bibcode : 2024EPJWC.30001006C . doi : 10.1051/epjconf/202430001006 .
• コーエン、J.、スチュワート、I. (1984). 『混沌の崩壊：複雑な世界における単純性の発見』バイキング・プレス。ISBN 0670849839。

• 複雑性尺度― あまり役に立たない複雑性尺度の多さについての記事。
• 科学技術における複雑性の探求（Wayback Machineに2011年3月5日にアーカイブ済み） – メラニー・ミッチェルによる複雑系入門コース
• 複雑系科学の研究に焦点を当てたサンタフェ研究所：講義ビデオ
• UC 4キャンパス複雑性に関するビデオ会議– 人間科学と複雑性