カーナビはどうしてルートを検索できるのか?～『P≠NP予想とはなんだろうゴールデンチケットは見つかるか?』L・フォートナウ氏（2014）

フォートナウ氏は計算複雑性の専門家、今のコンピュータを使えば何でも簡単に検索できるのでしょうか?（2014）

カーナビはどうやってルートを計算するか？

シカゴから車でニューヨークへ行きたいとしよう。GPSに住所を入力すれば、１，2分フンでシカゴからニューヨークまでのもっとも早いルートが見つかるので、それで出発だ。アメリカ全土の道路地図は数メガバイトのメモリーに収まるが、その地図上で考えられるルートの数はもっとずっと多い。

シカゴとニューヨークのあいだにルートはいくつあるだろうか？車が逆方向へ進まないという条件を付けたとしても、控えめにざっと計算しただけで、１のあとに0が63個続く数以上のルートが考えられる。それでもGPSは、そのすべての選択肢を調べ尽くす時間などないというのに、もっとも速いルートを見つけてしまう。

所要時間には興味深い性質がある。中間地点として、たとえばピッツバーグを選んでみよう。シカゴからピッツバーグを経由してニューヨークへ行く最短ルートは、シカゴからピッツバークへの最短ルートとピッツバーグからニューヨークへの最短ルートをつなげたものにほかならない。ピッツバーグを経由しないルートのなかにはもっと速いものもあるが、シカゴからニューヨークへの最短ルートが、シカゴからピッツバーグ経由でニューヨークに行く最短ルートよりも長いことはありえない。

GPSに使われているコンピュータプログラムは、このような性質を使って最適ルートを素早く絞りこんでいく。…最短ルート問題から分かるのは、たとえ選択肢の数が膨大であっても、必ずしもそのすべてを調べる必要はないということだ。（12ページ）

最短距離問題

ある2地点のルートを選択する場合、無数にあるルートに例えばハブとなる都市としてピッツバーグを選択するなど、軽重をつける。これによって数分で最適ルートを導き出せる。一方すべてのルートを同等と考え、総当たりで調べていくと選択肢が指数関数的に増えて数分はおろか、何時間かけても答を出すことができない。コンピュータサイエンスではP≠NPとして知られている問題である。

P≠NPとは

Pとは多項式時間（polynomial time）とはほどほどの時間内に答を出すことのできる問題の集まり。たとえば二つの数の掛け算は、数が大きくなればもちろん長い時間がかかるようになるが、そんなに急激に長くなるわけではない。

一方NP非決定性多項式時間（Non-deterministic Polynomial time）とは、答を出すのにどのくらい時間がかかるかは不明だが、出た答が合っているかどうかを比較的短い時間でチェックできる問題。PはNPに含まれるが、P＝NP 、P≠NPのいずれもが証明あるいは否定されていない。証明はされていないが、多くの数学者はP≠NPであると考えている。限られた時間内の計算によってすべてを計算し尽くすことはできない、ということである。