前回の続きです。
まずは、おさらいを兼ねつつ・・・
４１×２３＝？？
答 ９４３
のような問題や図形などの問題も含め、無理やりでも何でも良いので、現実的な時間で正しい答えが求められるような問題のグループを
「クラスP」
そして、
？×？＝９４３
⇒答 ４１と２３
の問題のような「クラスnP」のなかでも、「ハミルトン閉路問題～松下浩明「グラフ理論とアルゴリズム」より」のような、解くには運よく答えを見つけないと、膨大な時間をかけても解くことができないが、答えを聞けば「正解だ。」とすぐわかるような問題のグループを「ｎP完全」と呼んでいます。
この２つの問題は、「確実に解ける問題か？否か？」という点では完全に別物ですが、
※専門家の方々へ・・・
普通の中学生向けに書いているため、正しい説明にはりきっていません。
この「nP完全」に，まだ見つかっていない別の解きかたがあり、実は普通に解くことができるなら、実は「クラスP」だったということで、
P＝ｎP
になります。
逆に、別の解き方なんてなく、「運よく見つける以外に解くことが不可能。」なら、「クラスP」と「クラスｎP」は別物なので
P≠ｎP
になります。
現在のところは証明はされていませんが、
たくさんの世界最高レベルの研究者が一生をかけて考えているのに、まだ見つかっていないので、
P≠ｎP
じゃないのかな・・・・
と予想されています。
さて、これが何故、「100万ドルもの懸賞金がかけられている問題なのか？」というと、現代社会の根幹に関わる話だからです。
特に、
？×？＝９４３
⇒答 ４１と２３
に限って言えば、確実な解き方を発見されないほうが、すご～く良いんですね・・・
もし、どんな数字でも、うまく見つける方法がわかったら、私にこっそり教えてください！
自分が100万ドルの懸賞金を頂きます(笑)
それは冗談にしても、この問題は、「解けないほうが良い。」という、不思議な問題です。
みなさんは、「なんで？」と思うでしょうね・・・
興味のある人は、次回のブログ更新まで、ちょっと考えてみてみて下さい。
※「コンピューターを使ったとしてもほぼ不可能。」これがヒントです。
次回、「９４３の因数分解が、できないほうが良い理由」につづく。