「P≠nP予想」・・・②
前回のブログの続きです。
前回は、
①４１×２３＝？
は、ちょっとした時間があれば
４１×２３＝９４３
と答えられるけど、
②？×？＝９４３
の『？』を見つけるのが厄介ですが、このブログを見てきた人は４１と２３だ！とすぐにわかりますよね。
という、話まででした。
上の
①のような、現実的な時間で正しい答えが求められるような問題のグループを「クラスP」
そして、
②のような、運よく答えを見つけないと解けないけど、答えを聞けばすぐに正解である事が確認できるような問題のグループを「クラスｎP」
※専門家の方々へ・・・
普通の中学生向けに、噛み砕きすぎた内容にしてるため、正しい説明にはりきっていません。ご了承ください。
と呼んでいます。
まぁ、掛け算して３桁になるくらい値なら、１００万回ほど試し計算すれば答えは確実に求められます。
コンピューターの手をかりたなら、すぐに求められるでしょう。
ですが、これが大きくなればなるほど膨大な時間が必要になり、100桁以上になった値では現実的な時間内に解く方法は見つかっていません。
コンピューターを使ったとしてもほぼ不可能です。
最新の研究でも、多少効率よくする考え方は編み出されてはいますが、基本的には適当な数字をカンで当てはめて運よく見つける解き方で、確実に解くには膨大な時間が必要になります。
ちょっと前の話ですが・・・
2003年に行われた「RSA Factoring Challenge」という世界最高峰のコンテストで、
(自然数)×(自然数)＝(174桁の数値)
※正確には、「自然数」ではなく、「素数」と呼ばれる数です。
になる数を見つけるのに、
「業務用コンピュータ」を「100台」使って「３ヶ月」かかったそうです。
この、「掛け算して数値が○○になる２つの数を見つける。」というのは、因数分解でも必要なことですよね。
中学数学では見つけやすい数字設定をしているから、ここまで厄介な話にはなってないけど、基本的性質は同じです。
だから、因数分解は本当に「たくさん解いて、経験からくる勘を身に付けよう！」です。
中学の数値設定なら、１問１０秒以内！
たくさん解けよ！
「P≠ｎP予想」・・・
まだまだ続きます。
書き始めてしまったからには、完結させないと・・・
勢いで書き始めてしまったことに、ちょっと後悔しています（汗