複雑性 特定分野で

ウィキペディア

複雑性

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

特定分野での意味

科学のいくつかの分野では、「複雑性」は次のような意味を持つ。

• 計算複雑性理論では、アルゴリズムの実行に必要となる計算資源の量を研究する。「複雑性」を「計算量」とも呼び、具体的問題を最適なアルゴリズムを使って解くのに要するステップ数をその問題の入力の長さ（例えばビット数）の関数として表したものを時間計算量と呼ぶ。また、具体的問題を最適なアルゴリズムを使って解くのに要するメモリ量（例えば、テープ上のセル数）をその問題の入力の長さ（例えばビット数）の関数として表したものを空間計算量と呼ぶ。これによって計算問題を複雑性クラス（P、NPなど）に分類する。マヌエル・ブラムは計算複雑性理論の公理的手法を開発した。それによると、時間計算量や空間計算量といった具体的な複雑性尺度の多くの特性を公理的に定義された尺度の特性から演繹できる。
• アルゴリズム情報理論において、文字列の「コルモゴロフ複雑性」とは出力がその文字列に一致するプログラムの長さの最小値である。ブラムの公理に基づいたコルモゴロフ複雑性の公理的アプローチは、Mark Burgin が論文で提唱した。公理的アプローチは他の手法も包含している。そして、公理的に定義された一般化されたコルモゴロフ複雑性の特殊ケースとして様々な種類のコルモゴロフ複雑性を扱うことができる。様々な測度について例えば基本不変定理のような似たような定理を個別に証明する代わりに、この公理的設定で証明した1つの定理から個別の証明を演繹することができる。これは数学における公理的手法全般に言える利点である。コルモゴロフ複雑性の公理的手法は書籍で詳細化されており、それをソフトウェア測定法に応用した例もある。
• 情報処理において、複雑性とはオブジェクトが送信し観測者が検出した属性の総数の尺度である。このような属性の集合体を「状態」と呼ぶ。
• 物理的システムにおいて、複雑性とはシステムの状態ベクトルの確率の測度である。これはエントロピーとは異なる。
• 数学において、Krohn-Rhodes complexity は有限半群とオートマトンの研究で重要な概念である。

他にも次のような複雑性がある。

• 人間が問題を解こうとしたときに感じる問題の複雑さについては、認知心理学で hrair limit と呼ばれる複雑性の限界がある。
• 複雑適応系は、以下のような特性（一部または全部）を持つシステムである。
  • システム内の部品数（および部品の種別数）と部品間の関係の数は自明ではない。ただし、自明か自明でないかを区別する汎用的規則は存在しない。
  • システムにはメモリまたはフィードバックがある。
  • システムは自身の履歴やフィードバックに従って適応する。
  • システムと環境の関係は自明ではないか、または線型ではない。
  • システムは環境に影響され、自ら環境に適応する。
  • システムは初期条件に大きく左右される。