P≠NP予想とは何かをまとめた
プログラミングを始めてある程度の時間が経つとどうしても「P≠NP予想」という言葉を目にする。しかし実際にどういうものなのかを調べてみても全くわからない。
Wikipediaを見ても
http://ja.wikipedia.org/wiki/P%E2%89%A0NP%E4%BA%88%E6%83%B3
クラスPって何？Javaのクラスと違うの？
とか
多項式時間って何だよ
とか思ってしまって...
とにかく全くわからない。
んで
学校の図書館に数学ガールがあったので手にとってみると
この問題についてある程度詳しく書かれていたのでまとめてみる。
P≠NP予想とは何か
Wikipediaをそのまま引用すると
http://ja.wikipedia.org/wiki/P≠NP予想
P≠NP予想（P≠NPよそう、英: P is not NP）は、計算複雑性理論（計算量理論）におけるクラスPとクラスNPが等しくないという予想である。
だそうだ
ではクラスPとは何かというと
「多項式時間で解が求められる問題の集合のこと」
では多項式時間とは何か
多項式時間で解ける問題とは
解くのにかかる時間がO(n^c)である問題のこと
それだけ
改めてクラスPとは何かというと
「O(n^c)で解が求められる問題の集合」のことである。
では今度はクラスNPとは何かというと
「yes となる証拠が与えられたとき、その証拠が本当に正しいかどうかを多項式時間で判定できる問題の集合」
のことだ。
http://ja.wikipedia.org/wiki/NP
要は解の候補が与えられた時にそれが正しい解なのかどうかを多項式時間で”判定できる”問題のこと。
これについて注意すべきことがある。
解が”求められる”のではなく、解の候補が正しいかどうかを多項式時間で”判定できる”問題であるということと、
NPはNon-deterministic Polynomial time（非決定性多項式時間）の略であり、決して「解が求められない問題」ではないということだ。
P問題がNP問題に含まれることはすでに証明されている。
言い換えると
「多項式時間で解を求められる問題は、解の候補が与えられたときその解が正しいかどうかを多項式時間で判定可能である」
ということがすでに証明済みであるということだ。
ではその逆はどうか。
NP問題はP問題に含まれるか。
これがP≠NP予想である。
P問題がNP問題に含まれることは証明済みなので、
仮にNP問題がP問題に含まれた場合、P=NPだといえる。
そうでないのならP≠NPだといえる。
P≠NP予想を解く鍵の一つに
というものがある。
NP完全問題のうち一つでもP問題であるものが存在すれば、その時点でP=NPなんだそうだ。
つまり、NP完全問題のうち一つでもO(n^c)で解を求められるものが存在すればその時点でP=NPだということ。
NP完全問題は世界中にたくさんある。
充足可能性問題やハミルトン閉路問題などがそうだ。
このうち一つでもO(n^c)で解ければコンピュータ世界や数学界などいろいろな分野での大発見なのだが
世界中のコンピュータ科学者たちがいくら挑んでもNP問題をO(n^c)で解くことができないので
P≠NPだと予想されているということである。
この記事のほとんどは数学ガールの第4弾、「乱択アルゴリズム」で説明されているので読んでみるといい。
NP完全問題の定義を私は理解できていないのでこれから勉強する。理解でき次第記事にする。
今日はここまで。
