【けいさんりょうくらす】
計算量クラス とは？
最終更新:
💡 問題を、必要な時間やメモリの増え方で分類
問題を解く時間や使うメモリの増え方で分類する枠組み。P・NP・NP完全・PSPACEの意味と、理論上の分類と実際の速度の違いを説明します。
📌 このページのポイント
- 入力の大きさに対する計算資源の増え方で分類
- Pは多項式時間で解ける判定問題のクラス
- NPは「はい」を示す証拠を多項式時間で確認できる
- PはNPに含まれ、同じクラスかは未解決
ひよこ 計算量クラスは、実行時間のランキング？
ペンギン先生 問題の入力が大きくなったとき、必要な時間やメモリがどのように増えるかで分類する枠組みだよ。PやNPでは、まず答えが「はい・いいえ」になる判定問題を考えるんだ。
ひよこ Pは、すぐ答えが出る問題？
ペンギン先生 入力の長さに対して、多項式時間で解ける判定問題のクラスだよ。例えば入力の大きさをnとして、nの二乗などで時間を抑えられる仕組みを考える。ただし、理論上Pに入ることだけで実際の処理が短時間になるとは限らないんだ。
ひよこ NPは、Pに入らない問題？
ペンギン先生 違うよ。NPは「はい」と答えられることを示す証拠があれば、それを多項式時間で確認できる判定問題。例えば、すべての頂点を一度ずつ通る経路があるかを考え、提示された経路が条件を満たすか確認する。PはNPに含まれるんだ。
ひよこ NP完全とNP困難は、何が違う？
ペンギン先生 NP困難は、NPのどの問題も多項式時間で変換して解くのに使えるほどの難しさを持つこと。NP完全は、その条件を満たし、さらにNPにも入る問題だよ。NPのすべてがNP完全というわけでもないんだ。
ひよこ メモリによる分類もある？
ペンギン先生 PSPACEは、多項式の大きさのメモリで解ける問題のクラスだよ。PはNPに、NPはPSPACEに含まれる。ただし、時間の上限とメモリの上限は別。PとNPが同じかどうかは、今も未解決の問題なんだ。
もっと詳しく知りたい人へ
NPなら、「いいえ」の答えも同じ方法で簡単に確認できる？
NPの定義は「はい」の場合の証拠を確認するものです。経路の候補が一つ条件を満たさないだけでは、条件を満たす経路が一つもない証明にはなりません。「いいえ」を示す証拠の確認は別に考えます。
NP完全の問題は、どんな入力でも解けない？
計算不能という意味ではありません。小さい入力や特別な構造を持つ場合には、実用的に解けることもあります。一般の場合に多項式時間で解く方法があるかは未解決です。必要な入力規模や精度、実際の処理時間を確かめます。
まとめ：ざっくりこれだけ覚えればOK！
「計算量クラス」って出てきたら「問題を、必要な時間やメモリの増え方で分ける分類」と思えばだいたいOK！
📖 おまけ：英語の意味
「Complexity class」 ＝ 計算の複雑さによる分類
💬 計算モデルと、時間や空間などの資源の制限を決めて問題を分類します。単にプログラムの実行秒数を順位付けするものではありません。