Mathematics
graph
problem
Theory
unsolved

未解決問題にチャレンジしていることを説明すること

はじめに

これはMath Advent Calendar 2017 23日目の記事として書いています。

背景

自分が「趣味:数学」と周囲に公言するようになり、どんな内容なのか聞いてくれる人が表れるようになってきました。「素数が好き」とかであればわかりやすいですが、「計算量」の話となると、うまく伝えるのがなかなか難しいのではないかと思います。

計算量とは

計算量とは、ざっくりいうと、「チューリングマシンで計算可能な問題において、その入力サイズに対して解を得るまでの計算回数の増加度合い」と表すことができます。

P vs NP 問題

計算量における未解決問題といえば P vs NP 問題ですね。これは、Yes/No で答えることのできる問題(決定問題)を解くのに要する時間が、入力サイズに対して多項式時間となるか(P$=$NP)、そうではないものがあるか(P$\neq$NP)を問う問題です。

居場所が無い?

この未解決問題、賞金がかけられています。しかし、現代数学の中心からすると、どの領域にも接しておらず、隅っこにひっそりと佇んでいるようなイメージがあります。

一方、コンピュータ界隈では組合せ最適化問題として関心が持たれているものの、コンピュータの実務に関わる人達にとっては、あまり馴染みが無いように見えます。

グラフ問題

自分が関心を持っている領域を一般の人にわかりやすく説明する必要が時々あります。そんなとき、自分はグラフ問題を用いて説明を試みています。

一筆書き可能性とハミルトン路問題

一筆書き

一筆書きは、「与えられたグラフにおいて全ての稜線を一度しか通らない経路があるか」を問う問題です。これは、グラフの各頂点の次数が全て偶数、もしくは次数が奇数となる頂点が2個のとき、一筆書きが可能とわかります。計算量は明らかに $O(n)$ ($n$は頂点数)となり、多項式時間で解けることがわかります。

ハミルトン路問題

これに対してハミルトン路問題は、「与えられたグラフにおいて全ての頂点を一度しか通らない経路があるか」を問う問題です。これは一筆書きで見られたような簡便な判定方法がまだ見つかっておらず、多項式時間では解けないと考えられています。P vs NP 問題は、これが本当に解けないか、あるいは多項式時間(勘弁)で解けるかを問う問題といえます。

僅かな違いが大きな違い

そして、一筆書きでは「稜線」だったものがハミルトン路問題では「頂点」に置き換わっただけなのに、その計算量に大きな違いが出て来る(かも知れない)というところがとてもおもしろい、という説明をしています。

まとめ

日本人ならば「一筆書き」はイメージし易いですし、そこからの差異が小さい「ハミルトン路問題」も理解し易いと思います。とはいうものの、計算が簡単/難しいということをうまく説明する方法を持ち合わせていないため、説明に窮していたりします。

かように、自分が関心を持っていることの内容を、そうではない人に伝えるのはとても難しいと感じています。