2025年06月04日 第8回
今回は多項式時間で解ける/解けないアルゴリズムについて，
また関連してクラスP/NPについてや，
P=NPだった時どうなるかについて学びました．
質問です．
クラスNPについて，
「解を一つ与えてそれが正しいかどうかを判定する時間が多項式時間の問題のクラス」と解釈したのですが，
この解釈で正しいでしょうか?先生の説明と言葉が少し違うので引っ掛かりがあります．
また，
P=NPだった場合について，
アルゴリズムの存在の保証と発見は別物だと思うのでRSA暗号などを突破するのは当分難しいと考えます．
次回触れますが，あっていると思います．
そうですね．
ただ，アルゴリズムが見つかって初めてPと言えるので，その時点で保証されています．
また，講義では触れませんでしたが，
NPの中で，どれくらい難しいかを考えることも必要になります．
その際，ある問題を他の問題に変換する (帰着といいます) ことで，
お互いの難しいさのレベルを考えますが，多くの問題は帰着できるので，
困ってしまいますね．
だんだん講義の話が難しくなってきて焦りを感じています．
レポートの提出期限が迫ってきているので復習をしっかりと行い，
期限に間に合うように頑張りたいです．
それは難しくならないとね．大学だし．
今回の講義では問題のクラスについて学びました．
やはり解きやすさなどといったいかに効率的かどうかが大事だと感じました．
多項式時間で溶けるアルゴリズムが発見されていないことを証明することの難しさという説目がしっくりきた．
くらすNP に関する言い回しが少し理解できなかったところがあるので，
次回までに復習しておきたい．
溶けるじゃなくて，解けるですかね．溶けてもいいですが．
分からないところは質問してください．
P≠NP問題について，
もし全ての問題が多項式時間で求めることができたら，
すなわちN=NPだったら，
情報の保護はどのようにして行えば良いのだろうかと思いました．
例えばRSA暗号やElGamal暗号は量子コンピュータによって解かれるようになるのが危惧されていますが，
一方で量子コンピュータでも解けないような暗号の開発もなされています．
しかし，
はたしてP=NPだったら，
どのような暗号を作れば良いのでしょうか…
いいコメントですね．どうすれば良いですかね．
懸賞金が1億円かけられてる問題として以前から知っていたNP問題を授業で行いました．
問題文自体は理解できたのでやはり数学は，
問題文が簡単なものは割と難易度が高い(とくに京大)という受験の噂を思い出しました．
そうですね．よくあることだと思います．
今日も面白い講義をありがとうございました．
私はPとNPの問題について身近に考えた時に，
人間は迷路やパズルを解く時，
直感という形でP＝NPを実現しているのではないかと思いました．
また，
仮にP＝NPが証明されたとしてもそのアルゴリズム自体がまだ見つからなかった場合，
暗号は安全なままであるのか，
さらには，
そのような状況は実際には存在し得るのか疑問に思いました．
直感ですか．ある意味そうかもしれませんね．
師はなぜコンピュータサイエンス序論を教えることになったのですか？
良いコメントですね．なぜでそうか．思い出しておきます．
今回は列挙法・クラスP・NPについて学びました．
特にNP問題について考えるとジグソーパズルやルービックキューブなどといった日常生活にも例が溢れていて，
はじめ聞いた時は非常に難しく感じましたが，
具体的な事例で嚙み砕くことによって理解を深めることができました．
次回以降もこの考えを意識していきたいです．
ジグソーパズルやルービックキューブは講義では出していませんが，
具体例を思い浮かべるのは大切ですね．
nの階乗の近似をスターリングの公式を使って行うメリットは何がありますか？直接nの階乗を計算するよりもオーバーフローなどを防げるのでしょうか？また，
ブルートフォース探索などの100年近くかかる計算を実際にやろうとしたら，
パソコンの物理的限界が先に来ますか？
階乗の計算は繰り返しなので大変ですが，スターリングの公式だと楽ですね．
今回は実際に計算するという話はしていませんが．．．
ブルートフォース探索というのは列挙法のことですが，
パソコンが100年もつかどうかはどうでしょうね．
今回の講義では，
問題のクラスについて取り扱った．
P,NP問題や，
公開鍵暗号など，
暗号理論に関連の深いワードも出てきて，
次回の講義がとても楽しみになった．
楽しみにしていてください．
今回の抗議でNP問題について学んだが，
直観では，
多項式と指数が一致するなんてありえないと感じるが，
それが同じだと考える人もいて，
世の中広いなあと感じました．
また，
次回からの暗号の授業について，
今のコンピュータがどのような暗号を使っているのかなど，
とても楽しみです．
同じだと考えるということではないです．
暗号もですが，入門なので，興味を持ったら，専門科目で深くやりましょうね．
P≠NP予想について，
名前だけは知っていたが，
ここまで計算機工学に関係のある分野だとは思わなかったのでとても面白かった．
ところで，
TSPの話を聞いて，
機械的に最短経路を見つけることは計算量が多くなりがちだということは理解できたが，
同時に，
なぜ人間は，
なんとなく最短経路の目星をつけることができるのか疑問に思った．
何を基にしてそのような勘を働かせているのか，
人間の勘はどこまで正確なのか，
正確さに個人差はあるのか，
この人間の勘を機械が再現することはできるのかなど，
色々と考えてみたら興味がわいてきた．
良い疑問ですね．ただ，最適解を出すのは難しいですし，
人間の直感が当たらないことはよくあることです．
今回は主に多項式時間と指数関数時間の二つのアルゴリズムについて学んだ．
今後，
この二つのアルゴリズムでは解けないような問題が出てくるのだろうか疑問に思った．
ありますね．
今回の講義で，
クラスNPに分類されている問題でも指数関数時間のアルゴリズムしか見つかってないだけでもしかしたら多項式時間のアルゴリズムでも解ける可能性があることを知り非常に面白かった．
可能性はありますね．見つけてください．
P=NPでも安全な暗号方式の研究などは行われていないのでしょうか．
良いコメントですね．次回触れますが，多分ないですね．
今この瞬間に発見されたとしてもわからない，
発見できたものをすぐに発表はできないしないことを考えると，
我々が信じていることももしかしたら別の事実があるかもしれないと思うと研究している人は偉大だなと思った．
その通りです．そして往々にしてあることなのですが，二人 (以上) の研究者が
同時に考えているということです．
ある問題に対して現実的に解くことのできるクラスPと現実的に解くことができないクラスNPに分けることができることを初めて知った．
PvsNP問題ではクラスNPに属するものがすべてクラスPであることを示すことができればP=NPまたはP≠NPであるかを調べることができる．
しかし，
ミレニアム懸賞問題ではあるが，
それを実際に行うのはほぼ不可能だと考えられる．
そのため，
理論的に証明するにはどのようにしてアプローチしていくのか気になったので少し調べてみたところ，
多項式時間還元という方法で，
NP完全であると示された問題に対して多項式時間で解くことができると示すことができた際に証明する事ができると知った．
けれども，
未だ未解決問題であるだけに，
NP完全である問題はクラスNPの問題よりも難しいものであるようで，
やはりこれでも示すことが難しいということが面白いと感じた．
正確には「現実的に解くことができない」と思われている，ですね．
講義でも説明したように，もしかすると現実的な時間で解くことができるアルゴリズムが
発見されるかもしれません．
今回の講義では問題のクラスについて学びました．
問題の解ける，
解けないはアルゴリズムの複雑さによって判断されるのではなく，
多項式時間のアルゴリズムで解けるか否かによって判断されると理解しました．
最近ちょうど，
Youtubeで見た数学に関する難問についての動画でN≠NP問題を見ていたので，
今回の授業で登場して嬉しかったです．
P≠NP問題ですね．理解してくれていると思いますが．
黒板を書く時のキーッという音が気になるので出来れば気をつけて欲しいです．
多項式時間のアルゴリズムが発見されている問題は解きやすいというのはわかったのですが，
具体的にどのような問題があったのでしょうか？講義中に既に触れていたらすいません．
そうですか．失礼しました．解きやすい問題の例は講義中にソーティングについて触れました．
大変すばらしい講義をありがとうございました．
私はやはりクラスNP≠クラスPだと考えてしまいます．
やはり師も同様な考えをお持ちですか？どのように考えても反例が一切思いつきません．
もしよろしければ意見を伺いたいです．
確かに難しいですね．どうでしょうか．飲みながら (飲まなくてもいいですが)
議論したいですね．
今日の授業も面白かったです．
クラスpとクラスnpの関係のついてよく考えてみようと思った．
そうですね．考えることが大切です．とても良いと思いますよ．
プログラミングをする上で計算手順を減らすには多項式で表される形にしなければならないことは理解できた．
暗号についてはあまりイメージがわかないので次回の授業も頑張りたい．
この講義は基本，入門の内容なので，深く入れませんが，逆に，初歩的なところから話をする予定です．
今日の授業も面白かったです．
TSPなどは，
二次元の簡単なモデルですが，
実際には三次元で，
他にも交通条件や非対称性も考えないといけないので，
現実にはもっと複雑なのが，
辛いところだと思いました．
コンピュターが爆発的に進化するか，
天才な研究者が多項式時間で解けるアルゴリズムを発見しないと近似的に解くしかないのは嫌なので，
ぼくが必ず見つけます．
なるほど，その通りですね．良く考えていますね．
そして，見つけてください．期待しています．
基本情報と応用情報を3年までに取りたいと思っているのですが，
父親にはITパスポートもとった方がいいと言われました．
ITパスポート，
とった方がよろしいでしょうか．
ITパスポートって一番優しいのではなかったですかね．
なので，基本情報と応用情報をとれば，それでも良いように思います．
もちろん，(全て)制覇するという意味では順番に取っておくのも良いかもしれません．
最近どの授業も抽象度が増してきて難しくなってきた．
例えば今回の授業においては，
クラスNPの非決定性チューリングマシンという単語が出てきただけで，
これはどういう意味なんだとよく分からなくなってしまう．
こういう時はいちいちその意味なんて気にせず，
これはこういうものなのだと受け入れて次に行くしかないのでしょうか．
次回ふれますが，講義では，非決定性チューリングマシンというとチューリングマシンの説明も必要なので，
NPの定義については別のものを紹介しました．
また，受け入れずに不明なところは質問に来てくれたら良いと思います．
大学の講義も，質問も合わせて，サブスクなので．
非決定性チューニングマシーンの正体が気になった．
どのようなプロセスで解の当たりをつけるか興味を持った．
詳しく説明するので来てください．
講義では，別の定義もお話ししました．
今回の講義では，
様々な問題がどのようにクラス分けされるのかについて学びました．
質問なのですが，
TSP問題の列挙法の解は(n-1)！で指数関数ではないが，
スターリングの公式で指数関数の形に近似できるから，
これは指数関数時間で解けるアルゴリズムになっているという認識で合っていますか?
そうですね．指数関数と考えてくれて良いと思います．
列挙数が階乗で表されるTSPの問題を列挙法で解を求めることは現実的に不可能であるということを理解することができた．
また，
指数関数時間で解ける問題のクラスを多項式時間で解けないと断定するのではなく，
まだ見つかっていないだけと解釈するのが面白かった．
もし，
今後指数関数時間で解ける問題が絶対に多項式時間では解くことができないということが証明されたら，
クラスNPが本当にnot polynomialなるのかなと思った．
そのときは，そのようになりますね．
多項式に出来ないことを証明するという話を聞いて，
小学生の頃アニメできいた悪魔の証明に関する話を思い出しました．
そこで調べてみたところ 悪魔の証明は中世ヨーロッパの法学者が発祥と書いてあったのですが，
本当に法学者が発祥なのか疑問を抱きました．
疑問を持つのはとても良いことですね．ぜひ調べてみましょう．
P=NPなどといった言葉は言葉そのものしか知らなかったため，
軽く概観を知れてよかった．
計算量に関する研究は気が遠くなりそうだと思った．
確かに気が遠くなるかも．
N≠NP問題は初めて聞いた単語だったが興味深い概念だったので講義資料に引用されていた小説も読んでみようと思った．
また講義内容には関係しない話なのですが，
JavaScriptを使えばCLASSの出席登録をエンターキーで提出できたり登録を忘れていると通知を送ってくれるchrome拡張を作れたりするんでしょうか．
P≠NPですね．紹介したのは東野圭吾さんの小説で，P≠NPが主題ではなく，
湯川先生が犯人をみつけるというものです．
今回の講義では，
TSPとスターリングの公式，
問題のクラスについて扱いました．
クラスNPがNot Polynomialの略ではない理由は理解できたのですが，
定義の部分が少し複雑に感じました．
指数関数時間のアルゴリズムを処理するには今のコンピュータでは時間がかかりすぎるため非現実的ですが，
素数を使うことでこのように処理に膨大な時間がかかる数値を意図的に作り出し暗号として利用しているのは面白いと思いました．
また，
少し前に富士通と理化学研究所が256ビットの量子コンピュータを開発したというニュースを見たのですが，
量子コンピュータが実用化したら指数関数時間のアルゴリズムであっても高速に処理できるようになるのか気になりました．
ポスト量子暗号というのもあるのですが，自分でも調べてみたらどうでしょうか．
P≠NP問題について，
P≠NPであると私は今回の授業を考えたが，
証明するのが難しいというのは非常にもどかしく感じた．
しかし，
P=NPであると考える学者もいると解説されていたので，
なぜそう考えるのか非常に興味が湧いた．
いろいろと考えはあるということで，これも大切なところですね．
問題を解く時間(計算量が多いか，
少ないか)によって問題を分類分けすることに驚きました．
質問なのですが，
次の問題はp問題か，
np問題かどちらですか？問題: ある駅から電車，
バス，
徒歩によって別の駅(出発点と目的地の駅は何回か乗り換えしないと着けないくらい遠いとする)に行くときの最短経路を求める．
この問題について私は，
電車，
バスの来る時間や乗り換えの方法など行き方が無限にあるのでnp問題だと思いましたが，
乗り換えアプリを使えば一瞬で方法がわかります．
つまりアプリはこの問題の最短解法を知っていることになりますが，
この時この問題はp問題かnp問題のどちらなのでしょうか．
途中の説明 (「着けないらい遠い」など) が定量的でないですが，
最短経路問題はPです．多項式オーダのアルゴリズムが見つかっているので．
講義でも説明しました．
Pとは解の探索が多項式でできるもので，
NPとは解の検索が多項式でできるものなのだとイメージできました．
東野圭吾さんはこのPvsNP問題を想像しやすくもシニカルな表現で表しており，
小説家はすごいなと思いました
「NPとは解の検索が多項式でできる」ではなくて， NPとは解の検証が多項式でできる，です．
スターリングの公式はそのまま覚えるのは難しいと思っていたが，
n!≈n^nと捉えると本質がすっきり理解できた. PとNPに関しては，
列挙木の縦方向は深さ優先で多項式オーダーの探索が可能であるが，
横方向は分岐が指数関数的に増大するため，
多項式時間で解くことが困難であるという観点を用いると解釈しやすく感じた.. もしP=NPであれば，
現在成り立っている暗号の多くが一気に破られる可能性があるというのはいつ聞いても恐ろしい. 逆にP≠NPであれば暗号は安全なままとなるのだろうが，
その証明の難しさには驚かされる.
必ずしも安全ではないです．実際，RSAはもうあまり強くないと評価して良いと思います．
私は元々p≠np問題を知っていて，
情報工学の暗号の分野に関わっていることは知っていましたが，
今回の授業でより深くしれました．
ここで質問なのですが，
最近は暗号化技術が進化していて，
暗号化の方法が変わりつつあると先生が話していたのを覚えたのですが，
どのようなものなのか知りたいです．
私が，「暗号化の方法が変わりつつある」というように話したかは不明ですが，
講義中に，サマーウォーズのことに関連して，RSA暗号だけが公開鍵暗号と思っているかもしれないが，
「は暗号化技術が進化していて」(最近ではなくかなり古い)
というようなことは言いました．
その例として，楕円曲線暗号のことを言いました．
今回はクラスについて学んだ．
P対NP問題について授業中だけでは理解が追い付かなかったので課題をやりつつ理解していきたい．
解きやすい問題はアルゴリズムが簡単ということではないという点は勘違いしやすいと思ったので忘れないようにしたい．
そうですね．解くために必要な時間ということです．
今日も面白い授業ありがとうございました．
昔に聞いたことあるP対NP問題についての話で非常に興味深かったです．
シンプルそうに見えますが大変奥深く，
まだまだ理解が足りていないとは思いますが，
復習でYoutubeの動画を探すなどしてなんとか少しでも理解できるようにしたいと思います．
分からなければ質問しにきてください．
クラスNPの問題を多項式時間で解けるアルゴリズムを探すという「多分ないけどないと言い切れない，
だからやる」感が18世紀の科学者の永久機関開発に似たロマンを感じて非常に興味を惹かれました．
ロマンですね．でも，多分ないと思っている人が多いので，だからやる感は，ないかも．
前回までと今回の講義で，
問題に対する解の総数や問題を解くのにかかる時間が多項式で表せるかどうかというところに，
非常に重要で大きな隔たりがあることがわかった．
スターリングの公式を用いて階乗を評価している点も興味深かった．
また，
NPを，
多項式時間で解けるかどうかはわからないが与えられた解が正しいかどうかはわかる問題という定義と，
非決定性コンピュータで多項式時間内に解ける問題という2通りの同値な定義ががなぜ存在するのか疑問に思った．
非決定性コンピュータはすべてのパターンを同時に検証できるが最適解を探すことはできないという点も不思議に感じた．
「非決定性コンピュータはすべてのパターンを同時に検証できるが最適解を探すことはできない」ではなくて
非決定性コンピュータを用いると多項式時間で解を求めることができる，です．
次回，再度触れた方よさそうですね．
あまり，
資格などについては深く考えていなかった部分があるので資格についての話がとても役に立った．
応用情報技術者の資格を取ると給料が上がる会社もあるという先生の発言は，
コメントを毎回読み上げてくださってるおかげだと感じた．
また，
前回質問した幾何学的な解法について，
近似で角度などを利用するとできるといった点が面白いと思った．
自分でも試してみたい．
そうですね．色々と考えてみるのが大切ですよ．
多項式の範囲で済む計算と指数関数の範囲にまで及ぶ計算の違いについてよくわかりました．
クラスNPについてそれが新しく発見される際には私のような人間には到底思いつかない革新的なやり方が出てくるのではと考えるととても興味深いと思いました．
何か革新的なものはでてきますし，ぜひそれを考えてください．
今回の講義では問題に対してどのような式で計算できるかを元に問題のクラス分けが出来ることを学んだ．
賞金が出る数学の問題として雑学のように名前を聞いたことがあったP対NP問題について，
今日初めて何について議論している問題なのか理解出来て楽しかった．
もしもP=NPを証明出来たらその途端世界中の様々なセキュリティが危険に晒されるというのはとても面白く感じた．
そうなってしまうと恐ろしいですね．
NP=Pであった場合，
暗号としてクラスNPに分類される問題を使って現実的ではない時間がかかるということを利用して安全性をたもっているため問題が生じるというのを聞いてなるほどと思った．
また多項式時間で解けるアルゴリズムが存在しないことの証明ができていないためNPの意味をあのように定義していることが最高に理系していて面白いと思った．
同様に僕が本田翼じゃない証明もできないので実質僕は本田翼ですね．
本田翼じゃないことは証明できるんとちゃう？
講義内でユークリッド距離という単語が出てきて知らなかったので調べてみたところ，
ユークリッド距離と同時にマンハッタン距離という概念が出てきた．
実際TSP問題を考える上ではユークリッド距離で考えざるを得ないが，
資料の例であったアメリカの大統領選挙の演説で回る経路を考えるとなった場合，
全都市を航空手段で回ることはないのでマンハッタン距離で考えなくてはならない，
加えて様々な要素（道の混雑具合，
航空機の待ち時間など）と気づき，
問題解決はより現実的でないと感じた．
ユークリッド距離って知らないのですか．．．失礼しました．
みなさんに紹介したアメリカ48都市は，マンハッタン距離ではなくてユークリッド距離ですね．
次回触れます．
列挙法を用いた時に宇宙齢で換算しても膨大な数値になってしまうことがやっぱりすごいなと思う．
P，
NP問題について，
授業で扱う前は全く知らなかったため，
新しいことを知れてよかった．
そういえば，
大学生になる前は色んな人に「大学は先生方の板書の文字が達筆すぎて読めないよ」とあんなに散々言われていたのに案外読めていることに気づいた．
前の席にいても視力の都合で時々数などが読めないが，
視力の問題なのでメガネを買い替えたいと思う．
私は先生の字が達筆でも読めますが，
友人には私の字が読めないと言われました，
悲しいです．
達筆すぎるからじゃない？
非決定性チューリングマシンというのが調べてもよく分かりませんでした．
NP問題もそれを使うと多項式で解けるのですか？暗号理論は何もよく分かってないので今まで以上に授業を頑張りたいと思います！過去の共テ対策のときに秘密鍵暗号方式より公開鍵暗号方式の方が，
名前的には安全性が低そうなのに，
実際は安全性が高いということを習って絶望してましたので．
クラスNPの定義については，もう一つ紹介したので，そちらで考えてくれたら良いですが，
クラスNPは，非決定性チューリングマシンを用いて多項式時間で解ける問題のクラスです．
昔読んだ小説の中でP≠NP予想を証明しかけた天才のキャラが登場していた．
その時にはそのすごさがわからなかったが，
今回の授業でどれだけ規格外なのかを理解した．
暗号を解くときにそれに使われている問題がわかっているのなら，
近似的に求めようとすることで，
解きやすくなるのかなと思った．
そうですか．どの小説か教えてください．
P≠NP問題について，
クラスNPの中には多項式時間で解けるアルゴリズムがいつか発見されるものと発見されることがないものがあるため，
PとNPが完全に一致しないということだという理解をしたのですが，
資料の東野圭吾の小説の説明ではそれとは違う説明をしていて混乱しました．
私の理解であっていますか？
次回，再度触れますが，講義でも説明したように，P⊂NPなので，この意味では，
「クラスNPの中には多項式時間で解けるアルゴリズムがいつか発見されるものと発見されることがないものがある」
というのは間違っていないと思います．イコールになることはない，という考えです．
今日も講義ありがとうございました．
最後のP = NP問題についてあまり理解できなかったので，
あとで自分で調べたいです．
今日の計算量で分かれるクラスを見て，
自分でコードをかくときも多項式計算で終えられるアルゴリズムを書くことを意識したほうが良いと感じました．
分からなければ質問に来てください．説明します．
クラスNPについて，
多項式時間で解けるアルゴリズムが存在しないのでなく，
まだ見つかっていないという定義を知れました．
よろしいと思います．
今回は，
nの関数における指数関数と多項式の計算量の違いと，
PとNPのクラスの違いを学んだ．
最近，
単一始点最短経路問題において従来のダイクストラ法より計算量が少なくすむアルゴリズムが考案されたニュースを見たので，
この例はクラスPであるが，
これまで効率的なアルゴリズムが発見されていないからといってP≠NPと断言はできないと感じた．
そうですね．どうなるか分からないですからね．
P対NP問題について初めて知ったこともありまだ理解が浅い部分があるので，
しっかりと復習をしたいと思います．
分からなければ質問に来てくださいね．
P≠NP問題，
とても面白いなと感じました．
いままでこういった視点で考えたことがなかったので刺激になりました．
色々と考えてみると良いでしょう．
p対np問題は名前だけ知っていましたがどういうものか知れて面白かったです．
量子コンピュータが実用的になってくれば，
指数関数時間かかる問題も多項式時間で解けると思うので，
別に証明しなくてもよくなるかと思いました．
ですが数学者という生き物のことを考えるとそれでも証明に挑みそうな気もします．
そうですね．証明は重要ですからね．
クラスNPのNがnotではないのが多項式時間で解けるアルゴリズムが発見されていないだけでないとは言い切れないからというのに納得した．
あまりよくわからなかったので自主的に調べて復習しようと思う．
自主的に調べるのはよいことですが，分からなければ質問してください．
コンピュータは人が見つけたアルゴリズムを解くときによく使われているが，
指数関数時間のアルゴリズムしか見つかってない問題の多項式時間のアルゴリズムを見つける際にコンピュータが役立つのかが気になった
文意を理解できていないかもしれませんが，何かの役にたつのは？
今日はPとNPについて学んだ．
「多項式時間で解けない問題が存在するか？」という問いは数学基礎論のゲーテルの不完全性定理に似ていると思った．
数学においては解けない問題は存在しないと思われていたが，
実際は存在した．
コンピュータ科学ではP≠NPと思われているとのことだったが，
解けない問題に取り組んで人生を棒に振る研究者が少ないのは良いことだと感じた．
ただ，
実際は多項式時間で解けるのにその方法の発見を諦めている可能性があると思うと沼にはまりかねない問題だと思った．
人生を棒にふるかどうかは不明ですし，また，棒にふることがよいことかどうかも何とも言えないと思います．
本日の授業では，
多項式時間のアルゴリズムで解くことのできる問題と指数関数時間で解くことのできる問題について学んだ．
いわゆるミレニアム問題の一種であるPノットイコールNP問題についても知ることができた．
現代でも証明されていない問題の上に現代のネットワークセキュリティが成り立っていると考えると不思議なものを感じた．
確かに不思議ですね．
今回の講義では問題にかかる計算量によるクラス分けについて学んだ．
実は今までP対NP問題のNPはnot polynomialだと思っていた．
この講義でこの間違いを正せてよかった．
ところで，
もしもの話にはなるが，
P=NPだったとして，
はたして効率的なアルゴリズムが見つかるのだろうか．
数学の話だが，
微分方程式の解は存在するがそれを求めることができないあるいは非常に困難なことがある，
と聞いたことがある．
それと同様に，
現実的な時間で解けるアルゴリズムが存在するが，
それを見つけられないということもあるのではないか．
いいコメントですね．次回触れたいと思いますが，どのように証明するかによると思います．
「計算量」「多項式時間」「P≠NP予想」といった言葉は今までぼんやり聞きかじった程度だったのですが，
今回までの授業で色々な問題の計算量について扱い，
実際に計算量が爆発する状況を考えることで実感を伴った理解ができたと思います．
授業内で「対称TSPよりも非対称TSPの方が解法が簡単になる」と仰っていましたが，
これは大雑把に言えばA→BとB→Aで移動コストが異なることで移動方向が定まるため解きやすいということでしょうか？ChatGPT, Google Gemini, Microsoft Copilotに「対称TSPと非対称TSPではどちらの方が解法が困難になりますか？」と質問したのですが，
3つとも「非対称TSPの方が対称TSPよりも解法が困難である」と返答するので気になっています．
そうですね．その考え方で間違っていないと思います．
私は，最適化問題の専門家に聞いた話なので，チャッピーたちが間違っているんじゃない？
次回触れますね．
P vs NP 問題というのは聞いたことがあったのでどういう問題なのかが授業で知れてよかったです．
次回から暗号の話が始まるということで，
楽しみです．
楽しみにしてください．
今回の講義では多項式と指数関数について学びました．
p対np問題は聞いたことがあったものの，
内容は知らなかったので，
とても興味深かったです．
次回の講義は暗号についてということなので楽しみです．
楽しみにしてください．
本日も楽しい講義ありがとうございました．
本日は多項式時間で解けるアルゴリズムであるクラスPと今は多項式時間で解けるアルゴリズムが発見されてないけど，
指数関数時間のアルゴリズムしかみつかっていない問題であるクラスNPについて学び，
その関係についてご教授いただきました．
次の講義も楽しみです．
楽しみにしてください．
PとNPについて，
最初はあまり理解できなかったけれど，
東野圭吾さんの小説の一節を読んだことにより，
より理解が深まったので良かったです．
東野圭吾さんに感謝ですね．
p問題がNP問題に含まれるという発想が思いつかなかったので，
すごく納得しました．
指数関数時間のアルゴリズムがもし見つかったらディズニーとかでどの順番で回ると効率的なのかなどが分かって便利になりそうだなと思いました！！
そうですね．そのようなことを考えているひとはいますね．
今回の授業では，
主に，
クラスPと，
クラスNPについて扱いました．
非決定性チューリングマシンが複数の状態をとりながら計算をすることで，
多項式関数であらわすことができないような，
関数での解を早く求めることができるということを聞き，
0か1の状態しか扱うことのできない古典コンピュータではなく，
様々な状態を扱うことができる量子コンピュータならば非決定性チューリングマシンのような挙動を実現できるのではないかと思いました．
そうですね．そのように考えられていると思います．
解があるか判定することと解であるか判定することとの違いがあるとわかった．
前者は指数関数時間がかかり後者は多項式時間がかかるため，
特に選択肢の数が増えると差が大きくなるとわかった．
理解してくれていると思います．
問題の難易度がアルゴリズムの複雑さではなく，
多項式時間での解法があるかどうかで決まる考え方が面白いと感じた．
またクラスPとクラスNPが同じであると仮定した時に生ずる問題も暗号につながってくるとわかってとても面白かった．
関係してきますね．
今日は前の方の席を取ることができなかったので文字がよく見えなくて苦戦したので気持ち，
もう少し大きく書いてくださると嬉しいです．
けれど今日のNP問題を説明してくださった際に図があってわかりやすかすかったです．
また逆にP＝NPと考えている研究者はP≠NPに対してはどのように考えを持ってそう考えているのか気になった．
了解しましたが，最前列空いてますよ．