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

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

一方、「NP問題」とは、解が正しいかを多項式時間で検証できる問題のことです。 NP問題の中には、多項式時間で正しい解を発見できるP問題もあれば、多項式時間で正しい解を発見できないP問題以外の問題もあります。 大事な点は、P問題の反対はNP問題ではありません。NP は Non-deterministic Polynomial (非決定的多項式) の略です。 実際には、NP問題の集合の中にP問題が含まれている状態で、$\mathrm{P} \subseteq \mathrm{NP}$ です。

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

そして、$\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