😊出会いの泉😊

この粘菌コンピュータ、
以前から疑問だったのですが、識者に問いたいところです。
粘菌が解いたのはNP問題ではなく、多項式時間で解ける「中国人郵便配達問題」ではなかったかと思うのですよね。そんな気がするというだけで根拠はありません。間違っていたらごめんなさい。

四色定理の五辺国の話が NP だったというのは初めて聞きますが、本当ですか？
何か参考になる文献ありますか？

念のためですが、「実際に与えられた地図をどう 4 色で塗るか」という問題ではなく、「五辺国の塗り足しのためにどのような場合分けをすればいいか」の話であってますよね。
前者の話なら NP なのは明らかですし、四色定理の証明方針を考えればおそらく P なんだろうと思います。
が、後者の話だとそもそも何を問題サイズ n とすればいいかもよくわからないので、P とか NP とかを判定する対象にそもそもできないんじゃないかと思います。

https://ja.wikipedia.org/wiki/%E5%9B%9B%E8%89%B2%E5%AE%9A%E7%90%86
の四色定理にこう書いてあります。ケンプの証明後11年して、5辺国に誤りが見つかって、それで、これは五色定理と呼ばれていたそうです。四色で十分かは、グラフ理論の未解決問題として残ったと書いてあります。

その後コンピュータを利用して、四色問題を「証明」したとあります。

ですからDD++様の認識でよいと思います。

そこで、五色定理はPですが、グラフ理論の未解決問題をコンピュータでしらみつぶしで「証明」したから、Pではなく、Non-Pつまり、NPじゃないかと私は、思いました。

NP 問題の NP って Non-P じゃないですよ？

はちべえさん。

話のスジがずれていたら申し訳ないですけれども。

巡回セールスマン問題において、
セールスマンが訪問すべき拠点が50箇所程度であったとして、
コンピュータがしらみつぶしに厳密解を求めるために要するに時間は、
宇宙開闢以来現在までの時間でも、とてとても足りない、お話にならないくらい桁違い、
そういうオハナシなのですよね？
くだんのNHKの番組で紹介されていた筈です。

ではひるがえって、
四色問題における不可避集合を、事実上、しらみつぶしに調べることは人間の手には余る、だからコンピューターを使った、
でもこれ、そんなに時間がかかるものだったのてをしょうか？
不可避集合の個数は2000弱。
巡回セールスマンの訪問先の50よりも遥かに多いです。
にもかかわらず、放電手続きは無事に完了しています。論文の付録に全パターンを書き下すことができました。
これ、ほんとに巡回セールスマン問題と同じくらい難しい問題なのですか？

日本語で「しらみつぶし」というイメージは私も共有しています。
しかしながら、数学における、NPは、単なるしらみつぶしではないことも、頭にいれて議論したいものです。

おまけ。
NPとは、非決定性多項式時間（Non-deterministic Polynomial time）であり、Not Pではない。 定義は、「非決定性チューリングマシンによって多項式時間で解くことができる問題」かつ、「yes となる証拠が与えられたとき、その証拠が本当に正しいかどうかを多項式時間で判定できる問題」

ええ、正確には、Non-d.... Pですよ。d....は忘れましたが・・・

Dengan kesaktian Indukmu様、こんばんは。

>NPとは、非決定性多項式時間（Non-deterministic Polynomial time）であり、

そうです。それです。

コンピュータの計算に4年かかったそうです。充分、長い時間だと思いますけれどね。
コンピュータの出力は、高さ1.2mあったそうです。つまり、論文はとてもエレファントな証明だったそうです。

たぶん、終わりがあるんだろうかという不安にさいなまれたと思いますが・・・

一晩考えてみました。
問題の大きさ n を、「n 個の領域がある任意の地図を 4 色で塗り分けるアルゴリズムは存在するか」という形で定義すれば、四色定理の証明方法が NP かどうかの議論を始められることに気付きました。
そして、コンピュータでのしらみつぶしは全体の国の数に影響されない方法での検索だったので、解の発見にかかる時間は明らかに O(n^0) です。
だから、四色定理の証明は P 問題ってことになる……で、あってますかね？

DD++様、こんばんは。

ケンプは、数学的帰納法を使っていました。n国の地図は、4色で塗れるとします。

そこで、色が塗られてないn+1国の地図を持ってきて、
１）2辺国を探します。まず、2辺国を消すと、n国の地図ですから、4色で塗れるはずですから、塗ります。
そして、2辺国を復活します。2辺国は2つの国に挟まれているので、あと2色ありますから塗れることができます。
n+1国の地図が4色で塗れました。

また、色が塗られてないn+1国の地図を持ってきて、
２）3辺国を探します。消します。すると、地図は4色で塗れます。そして、3辺国を復活します。３辺国は３つの国に挟まれているので、あと１色ありますから塗れることができます。
n+1国の地図が4色で塗れました。

また、色が塗られてないn+1国の地図を持ってきて、
３）４辺国を探します。消します。すると、地図は4色で塗れます。そして、４辺国を復活します。４辺国は４つの国に挟まれているので、もう色はありません。そこで、トリッキーなことをして、４色でぬれました。
n+1国の地図が4色で塗れました。

また、色が塗られてないn+1国の地図を持ってきて、
４）５辺国を探します。消します。すると、地図は4色で塗れます。そして、５辺国を復活します。５辺国は５つの国に挟まれているので、もう色はありません。

つまり、５辺国問題が復活するのです。P問題では、解けません。

＞問題の大きさ n を、「n 個の領域がある任意の地図を 4 色で塗り分けるアルゴリズムは存在するか」という形で定義すれば、四色定理の証明方法が NP かどうかの議論を始められることに気付きました。
そして、コンピュータでのしらみつぶしは全体の国の数に影響されない方法での検索だったので、解の発見にかかる時間は明らかに O(n^0) です。

数学的帰納法で、n国まで成り立つとしてますから、これは、問題ないでしょう？
では、n+1国のときに成り立つ証明がいるのではないでしょうか？
そうでないと、数学的帰納法が完成しません。

いやいや、数学的帰納法で簡単（P≠NP 問題の意味では）に証明できるから P 問題だという話です。

ケンプ、アッペル、ハーケンによる証明は、
「100 ヶ国の地図が全て塗り分けられることの証明」でもコンピュータで 4 年、
「1000 ヶ国の地図が全て塗り分けられることの証明」でもコンピュータで 4 年、
「10000 ヶ国の地図が全て塗り分けられることの証明」でもコンピュータで 4 年、
「100000000 ヶ国の地図が全て塗り分けられることの証明」でもコンピュータで 4 年、
でしょう？

今日、NHKのEテレで、午後9:30~より、「笑わない数学　ポアンカレ予想」が放送されます。

Wikipediaのポアンカレ予想より引用すると、
＊＊＊＊＊引用開始＊＊＊＊＊＊
ペレルマンは解法の説明を求められて多くの数学者達の前で壇上に立った。しかし、ほとんどの数学者がトポロジーを使ってポアンカレ予想を解こうとしており、聴講した数学者たちもほとんどがトポロジーの専門家であったため、微分幾何学を使ったペレルマンの解説を聞いた時、「まず、ポアンカレ予想を解かれたことに落胆し、それがトポロジーではなく（トポロジーの研究者にとっては古い数学と思われていた）微分幾何学を使って解かれたことに落胆し、そして、その解説がまったく理解できないことに落胆した」という。
＊＊＊＊＊引用終了＊＊＊＊＊

トポロジーとは、位相幾何学だそうです。

ポアンカレ予想は、宇宙がおおよそ丸くない場合はどういう場合があるかというサーストンの研究から、これを証明することになったと言ってました。現在の物理学の世界観では宇宙はトーラス構造だそうです。

つまり、宇宙がおおよそ丸いというのは、直接的には証明されてないようですね。

４色問題もケンプの証明後11年後間違いが発見され、チューリングのオートマトン研究から、ノイマン型コンピュータができる訳ですが、チューリングがオートマトンを研究しなければ、コンピュータもできず、ハーケンらのコンピュータを使った解決はなかったでしょうし、後100年くらいかかったかもしれませんし、永遠に未解決のだったかもしれません。

このように、未解決の問題もコンピュータというタイミングで、解決されたことからも、いつか準備が整うまで、待たされ、それから解決されるのでしょう。

また、ペレリマンの証明も、後何年かして、間違いが発見されるかもしれません。絶対はないのでしょう。

さて、来週の「笑わない数学」は、虚数だそうです。虚数の歴史ですね。

今日、NHKのEテレで午後9:30から「笑わない数学　フェルマーの最終定理」が放送されます。

フェルマーの最終定理は、早々に未解決問題になって、数学者から、見放されたのでしょう。皆、忙しいですからね。

それをひっくり返したのが、全く関係のないと思われていた谷山ー志村予想が、フライ・セールのイプシロン予想で、フェルマーの最終定理を解決するとなったのです。
wikipedia 「フェルマーの最終定理」より
＊＊＊引用開始
つまり、谷山–志村予想が証明されたならば、それはフェルマーの最終定理が証明されたことをも意味するのである(=完全証明への道がつながった)。
＊＊＊引用終了
となったのです。

今日、NHKのEテレで午後9:30から「笑わない数学　カオス理論」が放送されます。

ニューロ人工知能は、一つ一つの原子を扱う統計力学的発想ですが、この前、NHKのEテレの心の時代で、脳はカオスであるという話がありました。まあ、マクロな経験則からできた熱力学みたいなものですね。現実は、統計力学より、熱力学のほうがよく使われているようです。ニューロ人工知能もカオス理論で、大きく進展するかもしれませんね。ニューロの人工知能で、うまく行っているのはカブトガニの視覚の研究の応用である画像認識だけらしいですから・・・・

今日、NHKのEテレで午後9:30から「笑わない数学　暗号理論」が放送されます。

暗号理論は巨大な数の素因数分解が困難であることを元にしています。
そこで、素数生成式を探していると、
https://enpedia.rxy.jp/wiki/%E7%B4%A0%E6%95%B0
にたどり着きました。素数生成多項式は存在しないことが証明されているそうです。
でも、そこには、マチャセビッチの多項式が、存在しているという話です。
でも、実用性は全くないそうです。
しかし、マチャセビッチの多項式は、証明されているそうです。
矛盾してますが、・・・・・

マチャセビッチの多項式について調べてみましたが、何も矛盾しているとは思いませんでした。
はちべえさん、そろそろ「正しい」「間違っている」を自分勝手に決めつけて話すのをやめませんか。

DD++様、こんばんは。
＞はちべえさん、そろそろ「正しい」「間違っている」を自分勝手に決めつけて話すのをやめませんか。
わたしは、そんなことを言ってません。
＞素数生成多項式は存在しないことが証明されているそうです。
＞しかし、マチャセビッチの多項式は、証明されているそうです。
なので、
＞矛盾してますが、・・・・・
と感想を書いただけです・・・・・

さて、来週は、ABC予想です。これは、大変面白いので、期待してます。

余談です。

《暗号理論は巨大な数の素因数分解が困難であることを元にしています。》

んー。
「笑わない数学」では
RSA暗号しか説明しなかったのでしょうか？
公開鍵暗号は、他にもいくつかやりかたがあってですね、最近ではRSAには未来がないという考えを持つ人も増えつつあります。量子コンピュータが素因数分解を得意とするかもという懸念があるためです。その実装はまだまだ先ですが。

《暗号理論は巨大な数の素因数分解が困難であることを元にしています。》については
もうちょつと複眼的に興味を持っていただければ幸いです。

Dengan kesaktian Indukmu様、こんばんは。
ありがとうございます。

来週のABC予想は面白いですよ。
ちょっと、参考までに、
数学者は宇宙をつなげるか？ａｂｃ予想証明をめぐる数奇な物語
https://www.nhk.jp/p/special/ts/2NY2QQLPM3/blog/bl/pneAjJR3gn/bp/pzwyDRbMwp/

かけ算は簡単であるが、足し算はむつかしいということで、フェルマーの最終定理も足し算でなくて掛け算だったらたちどころに解決できるそうです。数学にはそういう問題がたくさんあって、望月さんによって、ABC予想が証明されたので、数学は大きく変わるとか・・・

あっそうだ、思い出しました。

RSA暗号で。
秘密鍵を p, q のふたつの素数とし、
公開鍵を N=p*q としたときに。
Nの素因数分解をせずに暗号文を復号し平文を求める方法がいくつか知られています。
ただし、p,q の取り方が下手くその場合にですが。

ビックリするのですが。
平文 X を暗号化したものを
此の投稿に限り、
X ^a
としましょう。
で、こうしてできた暗号文を、
さらに、公開鍵で繰り返し暗号化していきます。
(((……(X^a) ^a) ^a) ^a) ……^a
そうすると、それが
Xと等しくなってしまうことがあるそうです。
これを、繰り返し暗号化攻撃といいます。

回避するためには
秘密鍵 p,q の作り方を工夫する必要があります。特許もあるようです。

繰り返し暗号化攻撃の他にも
アタックのしかたが少なくないようで
RSAでの安全な 秘密鍵の作り方が工夫されているようです。