複雑性
社会科学では、ミクロな特性からマクロな特性が生じる現象を研究している。社会的複雑性などと呼ばれ、コンピュータシミュレーションを利用した研究が多い。
複雑系の振る舞いはしばしば、創発と自己組織化で説明される。カオス理論は初期条件を変化させることで複雑な振る舞いを生じるシステムの敏感さを研究している。
計算複雑性理論は、問題の複雑性、すなわち問題を解くことの困難さを研究する。問題はそれを解くアルゴリズムにかかる時間を問題の大きさの関数で表すことによって複雑性クラスに分類できる。当然ながら問題は難しいものも簡単なものもある。例えば、難しい問題ではその大きさに対して解くのに指数時間かかるアルゴリズムを必要とする。そのような問題として例えば巡回セールスマン問題がある。これを解くのにかかる時間は O ( n 2 2 n ) {\displaystyle O(n^{2}2^{n})} (ここで nはネットワークの大きさであり、セールスマンが訪問すべき都市の数)である。都市のネットワークが大きくなると、解である経路を求めるのにかかる時間は指数関数以上に急激に増大する。
問題が理論上解くことができるとしても、実際にはそれほど単純な話ではない。その問題は非常に長い時間とあまりにも大量の空間を必要とするかもしれない。計算複雑性理論には様々な観点があり、問題を解くのにかかる時間、メモリ、その他の資源を研究する。問題の複雑性を分析する上では、時間と空間が最も重要でよく研究されている。
理論上は解けるが、必要とする時間や空間があまりにも大きいため、事実上解こうとすることが現実的でない問題のクラスも存在する。そのような問題をイントラクタブル(手に負えない、処理しにくい)という。