こんにちは、毛糸です。
先日、こんなつぶやきが話題になりました。
『配達ルートの効率化』って典型的NP困難問題なのでこれが解決出来たらノーベル賞ものなんだけど賞金30万円で権利譲渡ってすげえな。
＞ヤマト運輸プログラミングコンテスト2019 – AtCoder https://t.co/dD1sAvHaO1— TAKE-C (@TAKEC_MARUTA) 2019年7月2日
このツイートのなかで「NP困難」という言葉が使われています。
調べてみると、この話題は「P≠NP予想」という数学の未解決問題に関係する話であることが分かりました。
本記事ではクロネコヤマトのプログラミングコンテストに関連する「計算理論」という数学の概念を概観し、このプログラミングコンテストがどんな問題に挑戦するものなのか、P≠NP予想という未解決問題とどんな関係があるのかについてまとめます。
なお、直感やイメージを大事にするために、数学的な厳密さを欠く部分がありますので、詳しく勉強したい方はテキスト等を参照してください。
計算理論とはなにか
NP困難という用語は、計算理論という数学の一分野における用語です。
計算理論とは「計算」を数学的に定式化し、コンピュータのような計算機と、計算機による計算手順（アルゴリズム）について考えることで、ある問題が「計算」可能かどうか、可能であるならそれはどの程度複雑なのか、といった問題を扱う分野です。
ある計算がどの程度複雑なのかという問題は、計算複雑性理論と呼ばれています。
計算複雑性理論では、データが\(n \)個与えられたときに、計算量が\( n\)と比べてどれくらいの大小関係なのか、ということを考えます。
たとえば、ばらばらに並べられた\(n\)個の自然数を昇順に並べる場合に、
隣どうしの数字の大小を比較して、昇順に並び替える
という手順（アルゴリズム）を考えたとき、並び替えの回数は\(n(n-1)/2\)回を超えることはないということがわかります。
これは「おおよそ」\(n^2\)と同程度の複雑さと考えることができます（これくらいのアバウトさでも十分意味のある分析になります）。
このように、計算複雑性理論では、データ数に関連してその複雑性を定量な尺度で評価します。
多項式時間アルゴリズムとクラスP、クラスNP
あるアルゴリズムがデータ数との関連でどれだけ時間がかかるか、という問題を考えたとき、ある多項式で表せる時間以内で解けるようなアルゴリズムを、多項式時間アルゴリズムといいます。
多項式時間アルゴリズムで解ける問題は、クラスPと呼びます。
また、ある問題の答えが「yes」だとわかったとき、それが本当に正しいのかを多項式時間で判定できる問題を、クラスNPと呼びます。
>>NP-Wikipedia
ある問題がNPである、といったときには、その問題の答えが与えられたときに、膨大な計算を要さずに答え合わせができる、と考えてよいでしょう。
NP困難な問題と巡回セールスマン問題
NPに属する問題（多項式時間で答え合わせができる問題）と同等、もしくはそれ以上に難しい問題を、NP困難な問題といいます。
NP困難な問題は、その検証に膨大な計算を要する場合があります。
NP困難な問題として有名なものに「巡回セールスマン問題」というのがあります。
巡回セールスマン問題とは、いくつかの目的地を巡回するセールスマンが、もっとも短い移動距離を達成するには移動したらよいか、を考える問題です。
巡回セールスマン問題はNP困難、つまり多項式時間では解けない複雑な問題であるということです。
ヤマト運輸プログラミングコンテスト
冒頭でとりあげたヤマト運輸は、AtCoderというプログラミングコンテストサイトで、巡回セールスマン問題と思われる問題を出題しています。
ヤマト運輸プログラミングコンテスト2019
その問題の概要は以下のとおりです。
本コンテストでは、私たちの取り組む課題の一つとして「宅配ドライバーの配達ルートの効率化」をテーマとして取り上げ、配達ルートの最適化問題を含む2問を出題いたします。
配達ルートの最適化という言葉から類推するに、ヤマト運輸の出題する問題はおそらく巡回セールスマン問題に何らかの実際的な制約を課した問題なのでしょう。
ヤマト運輸はこの問題の良い解決策が得られれば、彼らの物流ビジネスの効率化につながります。
しかし、巡回セールスマン問題は多項式時間では解けそうにない（計算量が膨大になる）問題ですので、ヤマト運輸の課題も、解くのは容易ではないと予想されます。
なお、このヤマト運輸はこのプログラミングコンテストについて、著作権を譲渡することを求めており、これがちょっとした批判の的になってるようです。
P≠NP予想
計算複雑性理論には、数学上の未解決問題が残されています。
それが「P≠NP予想」です。
P≠NP予想はクレイ数学研究所のミレニアム懸賞問題の一つとして100万ドルの懸賞金がかけられた未解決問題で、
クラスP（多項式時間で判定できる問題）とクラスNP（多項式時間で答え合わせができる問題）とは一致しない
という予想です。
>>P≠NP予想-Wikipedia
>>P≠NP予想-Wikipedia
「PならばNP」（判定できるなら答え合わせができる）は真なので、PはNPに含まれる（P⊆NP）ことはわかります。
しかし、PだけれどもNPでないような問題があるかどうか（つまりPはNPの真部分集合になるか、多項式時間では判定できないけど答え合わせならできる問題があるか）はまだ誰も証明したことがなく、未解決の問題となっているのです。
まとめ
計算理論における、多項式時間やクラスP、NPといった用語をまとめながら、NP困難な問題である巡回セールスマン問題とヤマト運輸のプログラミングコンテストの内容について説明しました。
この分野においては「P≠NP予想」という数学上の未解決問題があります。
ヤマト運輸のプログラミングコンテストでP≠NP予想が解決できるわけではありませんが、計算理論の「実践」のすぐ近くに、数学の未解決問題があるというのは、ロマンを感じませんか。
参考文献
本記事の内容（計算理論やアルゴリズム、P≠NP予想）に興味を持たれた方は、下記書籍が大変参考になります。読み物としても数学書としても楽しめる名著です。
リンク