計算理論
計算複雑性理論は、問題がコンピュータで解けるかどうかだけでなく、その問題の困難さを扱う。時間計算量と空間計算量という2つの観点がある。時間計算量とは計算にかかるステップ数、空間計算量は計算に必要とされるメモリ量に相当する。
あるアルゴリズムが必要とする時間と空間を分析するため、時間や空間を問題の入力量の関数として表現する。例えば、長い数列から特定の数を見つけ出すという問題は、数列が長くなればなるほど難しくなる。数列に n {\displaystyle n} 個の数があるとき、その数列がソートされていなければ、一個一個の数を確認していくしかない。この場合、この問題の解法の時間計算量は入力量に比例して増大するといえる。
これを単純化するため、O記法が使われる。こうすることで特定のマシンの実装を前提とすることなく、問題の本質的な計算量を扱うことができる。従って、上の例の時間計算量は O ( n ) {\displaystyle O(n)} となる。
計算機科学の中でも最も重要な未解決の問題は、NPと呼ばれる計算複雑性クラスの問題が効率的に解けるかどうかである。詳しくは、P≠NP予想を参照して欲しい。