Wikipedia

複雑性

複雑性（ふくざつせい、英: complexity）という用語は、多数の部品が入り組んで配置された何らかのものを特徴付ける言葉として使われる。科学として複雑性を研究するアプローチはいくつか存在しており、本項目ではそれらを概説する。

定義

編集

複雑性の定義は、「システム」の概念と結び付けられていることが多い。システムとは部品や要素の集合であり、その部品や要素には互いに関係があり、システム外の要素とは関係の質が異なる。多くの定義は、システム内の多数の要素の状態とその要素間の関係の様々な形態を表現するのが複雑性という言葉だと仮定する傾向がある。同時に、何が複雑で何が単純なのかは相対的であり、その場その場で変化する。

定義によっては、システムの特徴が指定されたとき、与えられたシステム状態に遭遇する確率の問題に焦点を合わせている。ウォーレン・ウィーバーは、システムの部品毎の属性が与えられたとき、システム全体の属性を予測する困難さの度合いを複雑性であるとした。ウィーバーの観点では、複雑性は組織化されていない複雑性 (disorganized complexity) と組織化された複雑性 (organized complexity) という2つの形態に分類される[1]。ウィーバーの論文はその後の複雑性の研究に影響を与えている[2]。

システム、複数の要素、複数の関係の型、状態空間といった概念を具体化するアプローチは、定義されたシステム内の識別可能な関係の型（およびそれらの関連する状態空間）の数を複雑性とすることを暗に示していると言えるかもしれない。

定義によっては複雑な現象やモデルや数式を説明するアルゴリズムとの関係が深いものもある。

マサチューセッツ工科大学のセス・ロイドは、複雑性の定義を32種類集めてプレゼンテーションしたことがあるという[3]。

組織化されていない複雑性と組織化された複雑性

編集

複雑性に関連した問題の1つは、無作為に選んだ事物の関係の豊富なバリエーションとシステム内の要素間の関係の概念的な区別である。システムには制約があり、要素のバリエーションも減少すると同時に、より一様または相関する関係や相互作用の識別可能な型 (regimes) を生成する。

ウィーバーはこの問題に気づいており、少なくとも予備的な方法でそれに対処した。それが「組織化されていない複雑性」と「組織化された複雑性」の区別である。

ウィーバーの観点では、組織化されていない複雑性は非常に多数の部品（例えば数百万やそれ以上の部品）を持つシステムから生じる。「組織化されていない複雑性」における部品間の相互作用は大部分が無作為に見えるが、システム全体の特性は確率論や統計学的手法により理解できる。

組織化されていない複雑性の好例として、コンテナに詰めたガスがある。この場合ガスの分子がシステムの部品に相当する。

ウィーバーの観点では、組織化された複雑性では部品間の相互作用は全く無作為的ではなく相関している。これらの非無作為的かつ相関的な関係は明確に区別される構造を生成し、それがシステムと呼ばれ、他のシステムと相互作用する。調整されたシステムは個々の部品にはない特性を明確に示す。主体的なシステム以外のシステムでこのような組織化された複雑性がある場合、何らかの「導きの手 (guiding hand)」が無いなら「創発」と言う事ができる。

システムが創発的特性を示すかどうかという点に、部品数はあまり重要ではない。組織化された複雑性のシステムがどのような特性を示すかは、モデリングとシミュレーション、特にコンピュータを使ったモデリングやシミュレーションで理解できる場合もある。組織化された複雑性の例としては、都市近郊の生活のメカニズムがある。この場合、システムの部品に相当するのは近郊に住む人々である[4]。

複雑性の源と要因

編集

組織化されていない複雑性の源は、システムの部品数が膨大で、システム内の要素間の相関が欠如していることである。

組織化された複雑性の源については今のところ統一的な見解は存在しないが、無作為的でないということは要素間に相関があることを暗示している。例えば、Robert Ulanowicz による生態系の扱いを参照[5]。組織化されていない複雑性と同じく、システムの部品数や部品間の関係の数が重要かもしれないが、重要か重要でないかを区別する統一的な規則は存在しない。

オブジェクトあるいはシステムの複雑性は相対的特性である。例えば、計算問題の複雑性を計算にかかる時間としたとき、テープが1本のチューリングマシンよりもテープが複数本のチューリングマシンの方が計算にかかる時間が少なくなる。ランダムアクセス機械はさらに時間を削減でき[6]、帰納的チューリングマシンは関数や言語や集合の複雑性クラスさえも減少させることができる[7]。このようにツールの選択が複雑性の重要な要因となりうる。

特定分野での意味

編集

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

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

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

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

複雑性の研究

編集

複雑性は我々の周囲に常に存在しているため、様々な科学分野で複雑系や現象の研究が行われてきた。実際、科学者によっては複雑なもの（無作為ではないが変化を示すもの）だけが興味に値するという者もいる。

日本語では「複雑」だが、英語では類義語として「complex」と「complicated」がある。これを今日のシステムに対応させれば、無数の相互接続された配管と効率的な統合ソリューションの違いに相当する[13]。つまり、「complex」は「independent」（独立した）の反対で、「complicated」は「simple」（単純な）の反対である。

このような考え方からいくつかの分野で複雑性が定義されてきたのに対して、最近では複雑性を研究する分野に学際的な再編成の動きが見られ、アリ塚の複雑性、脳の複雑性、証券市場の複雑性などの研究が行われている。そのような学際的分野の1つに relational order theories がある。

関連する話題

編集

複雑な振る舞い

編集

複雑系の振る舞いはしばしば、創発と自己組織化で説明される。カオス理論は初期条件を変化させることで複雑な振る舞いを生じるシステムの敏感さを研究している。

複雑な機構

編集

人工生命、進化的計算、遺伝的アルゴリズムといった分野では、複雑性や複雑適応系に重点を置いた研究が増えている。

複雑なシミュレーション

編集

社会科学では、ミクロな特性からマクロな特性が生じる現象を研究している。社会的複雑性などと呼ばれ、コンピュータシミュレーションを利用した研究が多い。

複雑系

編集
→詳細は「複雑系」を参照

システムの研究のひとつとしての、複雑 (complex) なシステム、すなわち複雑系 (complex system) の研究の歴史は長い。複雑系は生物的なもの、経済的なもの、テクノロジー的なものなど様々なものが存在する。最近では、実世界の社会認知的システムの研究も複雑系を扱っている。複雑系は高次元で非線形であることが多く、モデル化が難しい。状況によっては低次元の振る舞いをすることもある。

データの複雑性

編集

情報理論において、アルゴリズム情報理論はデータとしての文字列の複雑性を扱う。

複雑な文字列は圧縮しにくい。直観的には、文字列の圧縮率は採用したコーデックで変わってくると思われる。コーデックは理論的には任意の言語について作成でき、中には非常に小さいコマンド X が非常に長い記号列（例えば 18995316）を生成するものもありうる。任意の2つのチューリング完全な言語は互いを実装できる。2つの言語による符号化の長さは変換言語の長さを上限として様々となるが、データ文字列が十分大きければその差はほとんど無視できる。

アルゴリズム的な複雑性の尺度は、無作為なノイズに高い値を割り当てる傾向がある。しかし、複雑系を研究する分野では無作為性と複雑性を区別して扱う。

情報量も複雑性の尺度として情報理論で使われることがある。

複雑性の応用

編集

計算複雑性理論は、問題の複雑性、すなわち問題を解くことの困難さを研究する。問題はそれを解くアルゴリズムにかかる時間を問題の大きさの関数で表すことによって複雑性クラスに分類できる。当然ながら問題は難しいものも簡単なものもある。例えば、難しい問題ではその大きさに対して解くのに指数時間かかるアルゴリズムを必要とする。そのような問題として例えば巡回セールスマン問題がある。これを解くのにかかる時間は  （ここで nはネットワークの大きさであり、セールスマンが訪問すべき都市の数）である。都市のネットワークが大きくなると、解である経路を求めるのにかかる時間は指数関数以上に急激に増大する。

問題が理論上解くことができるとしても、実際にはそれほど単純な話ではない。その問題は非常に長い時間とあまりにも大量の空間を必要とするかもしれない。計算複雑性理論には様々な観点があり、問題を解くのにかかる時間、メモリ、その他の資源を研究する。問題の複雑性を分析する上では、時間と空間が最も重要でよく研究されている。

理論上は解けるが、必要とする時間や空間があまりにも大きいため、事実上解こうとすることが現実的でない問題のクラスも存在する。そのような問題をイントラクタブル（手に負えない、処理しにくい）という。

関連項目

編集

脚注・出典

編集
  1. ^ Weaver, Warren (1948), “Science and Complexity”, American Scientist 36: 536 (Retrieved on 2007–11–21.), http://www.ceptualinstitute.com/genre/weaver/weaver-1947b.htm 
  2. ^ Johnson, Steven (2001). Emergence: the connected lives of ants, brains, cities, and software. New York: Scribner. pp. p.46. ISBN 0-684-86875-X 
  3. ^ Lloyd, Seth (2006). Programming the Universe. Knopf. ISBN 978-1400033867 
  4. ^ Jacobs, Jane (1961). The Death and Life of Great American Cities. New York: Random House 
  5. ^ Ulanowicz, Robert, "Ecology, the Ascendant Perspective", Columbia, 1997
  6. ^ Greenlaw, N. and Hoover, H.J. Fundamentals of the Theory of Computation, Morgan Kauffman Publishers, San Francisco, 1998
  7. ^ a b Mark Burgin (2005), Super-recursive algorithms, Monographs in computer science, Springer.
  8. ^ Blum, M. (1967) On the Size of Machines, Information and Control, v. 11, pp. 257-265
  9. ^ Burgin, M. (1982) Generalized Kolmogorov complexity and duality in theory of computations, Notices of the Russian Academy of Sciences, v.25, No. 3, pp.19-23
  10. ^ Burgin, M. and Debnath, N. Hardship of Program Utilization and User-Friendly Software, in Proceedings of the International Conference “Computer Applications in Industry and Engineering”, Las Vegas, Nevada, 2003, pp. 314-317
  11. ^ Debnath, N.C. and Burgin, M., (2003) Software Metrics from the Algorithmic Perspective, in Proceedings of the ISCA 18th International Conference “Computers and their Applications”, Honolulu, Hawaii, pp. 279-282
  12. ^ Johnson, Neil F. (2007). Two’s Company, Three is Complexity: A simple guide to the science of all sciences. Oxford: Oneworld. ISBN 978-1-85168-488-5 
  13. ^ Lissack, Michael R.; Johan Roos (2000). The Next Common Sense, The e-Manager’s Guide to Mastering Complexity. Intercultural Press. ISBN 9781857882353 

参考文献

編集

外部リンク

編集
「https://ja.wiki.x.io/w/index.php?title=複雑性&oldid=96915854」から取得