スポンサーサイト 

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

解けたら100万$ P≠NP予想 

『P≠NP予想』

2000年にクレイ数学研究所のミレニアム懸賞問題の一つとして、
この問題に対して100万ドルの懸賞金がかけられています。

その内容は、

一般的な解法がある問題と
一般的な解法がなく、全通り虱(しらみ)潰しに調べるしかない問題の2通りがある

って予想です。


■P(Polynomial)問題

一般的な解法がある問題。

例1)
『x^2-3x+2=0 を満たすxを求めよ』

※ 解の公式や因数分解を知っていれば、すぐに(1,2)と分かります。

例2)
『1から10までの数字を2組に分けて各組の積をとった場合、
 その積が等しくなる分け方が存在するか』 (森博嗣:すべてがFになる より)

※ 問題を見た瞬間、
 全ての組み合わせ(Σn=1~5 10Cn = 637通り)を考えないといけない感じですが、
 素数7を持つのが7だけということに気づくと、
 すぐにそんな分け方は存在しないことが分かります。

■NP(Nondeterministic Polynomial)問題

一般的な解法がない問題。

例3)
『12345678901は素数か』

※小さい自然数から順番に素数か調べていくしか無い問題です。
 簡単に求められる方法があれば、P問題なのですが。。。

例4)
『すべての道はローマに通じるという諺があるが、それは何通りか』

※正直、全ての経路考え、数えていく方法しかないです。。。


■P≠NP予想

以上を踏まえると、P≠NP予想は、

「P問題とNP問題は違うという予想」

であり、

「P問題とNP問題は区別できる予想」

とも言え、

「P問題とNP問題の2通りが存在し、
 あらゆる問題はそのどちらかに属するという予想」

となります。


例3のように、
素数を見つけるなんて、虱潰しにする方法しか思いつきませんし、
そんなの当たり前のようなことですが、
虱潰しの方法しかないという証明をした人はありません。


。。。。。。。。。。。。。。。。。。。。。。。。。


実用例を考えて見ます。

世間的に『解法が無いほうが都合がいいもの』として、暗号が考えられます。

ところが、残念ながらこの予想が外れて
P=NP(全ての問題には、一般的な解法が存在する)ってことになったらどうでしょう。

全ての暗号は一般的な解読法(キー)があり、
完璧な暗号は作れないってことになってしまいます。

そんなことになると、困ったものですね。

実際は、暗号は虱潰しに調べるしかないのですが、
本当にその方法しかないということを証明した人はいません。


。。。。。。。。。。。。。。。。。。。。。。。。。


この予想を見事に証明した暁には、
めでたく100万$の賞金がもらえます。

暇つぶしにいかがでしょう?

Comments

Comment Post















管理者にだけ表示を許可する

Trackbacks

Trackback URL
http://leaf64.blog48.fc2.com/tb.php/222-d31725bd

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。