12 - 一般名無し質問者 2022/02/08(火) 07:00:38 ID:7dw+Yp3h0
ある問題を解くプログラムの計算量のOの中身が多項式になる問題のクラスをPといい、計算量理論では簡単な問題であるという扱いになっています。
これまではプログラムの実行環境としてシングルコア、つまり同時に1つの計算の流れしかないことを前提としましたが、これを無限個に増やしたときに多項式時間で解ける問題のクラスをNPといいます。
（たぶんこれはNPの正式な定義と等価のはずですが、自信がないです。計算機科学に強芋による補足を切に望む）
Pに属する問題はNPにも属することに注意してください。無限にあるコアのうちの一つだけを使えばいいわけですから。
今説明したPとNPが実は同じであるかどうか？ はおそらく計算機科学で最も有名な未解決問題で、P≠NP予想と呼ばれています。
予想の名前から分かるように、多くの専門家はこの2つは異なる、つまりNPには属するがPには属しない問題があると考えています。
NP完全と呼ばれるNPのなかでは最も難しい問題のクラスがあり、これが1つでも多項式時間で解けるとP=NPが証明できます。
NP完全問題には実用上重要な問題も多くあり、たくさんの研究者たちが高速化に励んできましたがこれらの問題が多項式時間で解けたとする報告が一切なかったことが≠説の根拠となっています。
ちなみに、この問題には100万ドルの懸賞金がかかっています。解けたとしたらお金よりも人類の歴史に名前を刻むであろうその栄誉の方がはるかにすごいと思いますが、
専攻選びに悩んでいる高校生たちがこれをもし見ていたら、こういう夢のある理論計算機科学なんかいかがでしょうか。