NP困難の検索結果1 - 1 件 / 1件

• あとで読む

  うさぎでもわかるP vs NP問題（NP完全、NP困難の違い）

  • 6 users
  • www.momoyama-usagi.com
  • テクノロジー
  • 2021/02/25

  こんにちは、ももやまです。 今回は「P vs NP問題」について少しわかりやすめにまとめました。 この問題は、数学上の未解決問題となっており、2019年6月現在でも6つが解決していません。その問題の1つが「P vs NP問題」となっています。 これらの未解決問題は、アメリカのクレイ数学研究所によって、100万ドル（約1億円）の懸賞金がかけられています。*1トリビアの泉でも紹介されました。 No.681 「数学の世界には解くと賞金１億円がもらえる問題がある」 （番組評価 85/100へえ） もちろん「P vs NP問題」も懸賞金がかけられている問題の1つです。 そんな「P vs NP問題」とはどんな問題なのかをわかりやすく説明していきたいと思います。 ※注意 今回は問題はYesかNoかを判定する問題だけを考えます。このような問題を決定問題と言います。決定問題の例としては、 300円以内で50