計算複雑性理論
問題を「難しそうかどうか」ではなく、必要な時間とメモリの量で分類する計算機科学の一分野。
この分野を体系化したのはユリス・ハートマニスとリチャード・スターンズで、1965年のことだ。二人は分野に名前を付け、1993年にチューリング賞を受賞している。問題はクラスに分けられる。Pは多項式時間で解ける問題、NPは答えの候補が与えられたとき多項式時間で検証できる問題、PSPACEは時間を問わず多項式サイズのメモリで解ける問題である。分類の対象は個々の実装ではなく問題そのものであり、この点でビッグオーとは異なる。
実用上の価値は、探すのをやめどきを知ることにある。NP完全な問題なら、厳密で効率のよいアルゴリズムを探しても徒労に終わりやすい。ヒューリスティクスや近似、あるいは条件を絞った問題へ切り替えるのが賢明だ。暗号は逆の賭けで成り立っている。公開鍵暗号は、大きな数の因数分解を高速に解く方法が誰にも見つかっていないことに全面的に依存している。