コトバンクはYahoo!辞書と技術提携しています。

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

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

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問題はこれらの問題の一つとしてあげられている。(→組合せ論

出典|ブリタニカ国際大百科事典 小項目事典ブリタニカ国際大百科事典 小項目事典について | 情報

今日のキーワード

俳句甲子園

1998年から松山市で開かれる全国高等学校俳句選手権大会。高校生が5人1組で句の優劣をディベートで競い合う。チームでの勝敗とは別に、個人の最優秀句も選ぶ。今年は過去最多の41都道府県から121校、15...

続きを読む

コトバンク for iPhone

コトバンク for Android