P対NP問題（読み）ピータイエヌピーモンダイ（英語表記）P versus NP problem; polynomial versus nondeterministic polynomial problem

デジタル大辞泉

ピーたいエヌピー‐もんだい【P対NP問題】

コンピューターの計算理論における未解決問題の一つ。多項式時間以内で解けるアルゴリズムが存在するクラスPの問題と、多項式時間以内で効率よく解けるアルゴリズムは見つかっていないが、ある解があらかじめ与えられたとき、それが正しいかどうかを多項式時間以内で判定できるクラスNPの問題を考えるとき、クラスNPに属し、かつクラスPに属さない問題が存在するかどうか明らかではないというもの。すなわち、現実的な範囲の時間内で計算可能なクラスPと解の検証は可能であるクラスNPは同じではないという予想を意味する。ミレニアム問題の一つとしても知られる。P≠NP予想。P対NP予想。

出典　小学館

ブリタニカ国際大百科事典 小項目事典

P対NP問題
ピーたいエヌピーもんだい
P versus NP problem; polynomial versus nondeterministic polynomial problem

理論コンピュータ科学と数学における計算複雑性（計算の複雑さ。計算量）に関する問題。ある問題がクラスPであるとは，その問題を多項式時間（→多項式）で解くことが可能であることである。すなわち，問題解決のアルゴリズムにおけるステップの数が，入力データの長さの多項式関数で上から押さえられるということである。それに対してクラスNPとは，問題の答えが正しいという証拠が与えられたときに，それを多項式時間で検証可能であるという問題のクラスである。クラスPはクラスNPに含まれることは明らかであるが，P対NP問題とは，クラスNPがクラスPよりも真に大きいかという問題である。クラスNPに属し，クラスNPのほかの全問題が多項式時間に帰着される問題を NP完全という。1971年にアメリカ合衆国のコンピュータ科学者スティーブン・クックは充足可能性問題が NP完全であることを証明した。充足可能性問題とは，論理式において，すべての変数に真または偽をうまくあてはめることによって，全体の値を真にできるかという問題である。今日では多くの問題が NP完全であることが示されている。これらの NP完全問題の一つでもクラスPに属することが示されれば，P＝NP となる。P対NP問題は暗号理論とも深く関わっている。たとえば，暗号に用いられる大きな素数による素因数分解はクラスNPの問題であるが，もし P＝NP であることが示されれば，暗号の安全性が根本的に覆ることになる。2000年にアメリカのクレイ数学研究所は数学の七つの未解決問題をミレニアム問題として提出し，それぞれの問題に 100万ドルの懸賞金をかけた。P対NP問題はこれらの問題の一つとしてあげられている。（→組合せ論）

出典　ブリタニカ国際大百科事典 小項目事典