計算複雑性理論
計算複雑性理論で扱う問題とは、ある一連の問いの集合があり、各問いは有限長の文字列で表され、与えられた問いに対して解を求めて出力する計算問題である。例えば、FACTORIZE問題とは「二進数で書かれた1つの整数について、その素因数を全部求めて返す」という問題である。問題に属する個別の問いをインスタンスと呼ぶ。例えば、「15 の素因数を求めよ」は FACTORIZE 問題のインスタンスである。
アルゴリズムの計算量(けいさんりょう)とは、計算機がそのアルゴリズムの実行に要する計算資源の量をいい、アルゴリズムのスケーラビリティを示す。形式的には計算機をチューリング機械やランダムアクセス機械(random access machine)などの計算モデルとして定式化したうえで、アルゴリズムの使用する資源の量を入力データ長などに対する関数として表す。計算モデルの瑣末な詳細に影響を受けないよう、計算量はその漸近的な挙動のみに注目し、定数倍を無視するO記法で書き表すことが多い。計算モデルとしては、チューリング機械や論理回路などがある。計算資源の量としては、チューリング機械における時間計算量(動作ステップ数)や空間計算量(テープ長)、また論理回路における素子数や深さなどがある。
時間計算量は、あるアルゴリズムを使ったときに問題のインスタンスを解くのに要するステップ数を意味し、入力データの長さ(ビット数などで表現できる)の関数として表される。