晴耕雨読

working in the fields on fine days and reading books on rainy days

P問題とNP問題の違い

一言でまとめると、P問題は効率的に正しい解を発見できる問題で、NP問題は効率的に正しい解か検証できる問題のことです。

「P問題」とは、多項式時間で正しい解を発見できる問題のことです。 P は多項式 (Polynomial) 時間を意味し、計算量が $O(n^\alpha)$ の形($\alpha$ は定数)で正しい解を発見できることを意味します。

一方、「NP問題」とは、効率的に正しい解を発見できないが、ある解が正しい解であるかを多項式時間で検証できる問題のことです。 NP は Non-deterministic Polynomial (非決定的多項式) の略です。

例えば、10000桁の数字が与えられたときに、その約数の中に末尾が3のものが存在するか、という問題はNPです。 正しい解を得るためには10000桁の数字を素因数分解する必要がありますが、素因数分解を効率よく(多項式時間で)行うアルゴリズムはないので、発見はとても時間がかかります。 しかし、誰かが条件を満たす約数を見つけてくれたら、それが正しい解かどうかは、割り算した余りを見るだけで判断できるので、検証はとても簡単です。

上記から、P問題の集合 $\mathcal{P}$ はNP問題の集合 $\mathcal{NP}$ に含まれることは明らかです。 表にまとめると以下のようになるからです。

複雑性クラス1 $\mathcal{P}$ $\mathcal{NP}$
多項式時間で正しい解を発見できる はい いいえ
多項式時間で正しい解か検証できる はい はい

そして、$\mathcal{P} \ne \mathcal{NP}$ 予想は、P問題の集合とNP問題の集合は一致していないという予想です。 意味としては、効率的に正しい解か検証できるからと言って、効率的に正しい解を発見することは限らない、というものです。

もし $\mathcal{P} = \mathcal{NP}$ を証明できると「検証が効率よくできる」なら「発見も効率よくできる」となり、NP問題でもまだ見つかっていない効率よく問題を解くアルゴリズムが存在する可能を示唆することになります。 しかし、多くの研究者が長年にわたってNP問題を指数時間アルゴリズムより効率的な多項式時間アルゴリズムの開発に取り組んでいるにも関わらず、そのような効率的なアルゴリズムは見つかっていないことから、一般的に、$\mathcal{P} \ne \mathcal{NP}$ だと信じられています。

以上です。

参考文献

  • 複雑性クラス - Wikipedia
  • Ph.D. スコット・アーロンソン(著), 理博 森弘之(訳)『デモクリトスと量子計算』, 森北出版, 2020/09
  • 結城浩『数学ガール/乱択アルゴリズム』, ソフトバンククリエイティブ(株), 2013/8

  1. 複雑性クラスには N や NP 以外にも様々なものがあります。詳細は「複雑性クラス」で検索してみてください。その他でよく見るのは BPP(乱択アルゴリズムで多項式時間で解ける問題のクラス)や BQP(量子コンピュータで多項式時間で解ける問題のクラス)などです。