有名な Traveling Salesman Problem (TSP)
TSP の定義を簡単に述べると次のようになる。すなわち、
グラフ について、頂点
は辺
を持っており、各辺は重み
を持っている。この時に巡回路の重みの総和が最小となるものを求めよ。
多項式時間定数近似アルゴリズム
グラフ が与えられたとき、
最適解を
で表すことにする。同様に、アルゴリズム
の出力値を
で表すことにする。
あるアルゴリズム
について、任意の入力
に対して、
\begin{align} & ^\exists const \,\,c > 1, \, \, OPT(G) \leq ALG(G) \leq c OPT \end{align}
Hamilton Circuit から TSP
正の定数 が与えられているとする。
- 判定版 HC: ハミルトン閉路が存在するか
- 判定版 TSP: 合計の重み
以下の巡回路が存在するか。 について考える。
判定版 HC を考える。グラフ が入力であるとする。グラフ G の各エッジの重みを全て
に設定する。この操作によって判定版 HC の真偽が変わることはない。
このとき、グラフ G の補グラフ と完全グラフ
を考える。すると、
\begin{equation} E \cap \bar{E} = \phi, \,\, E \cup \bar{E} = E_c \end{equation}
となる。また、 として、補グラフのエッジの重みを全て
と設定する。すると、両者を合わせた完全グラフ
は、
に含まれる辺の重みは 1 で、含まれない辺の重みは 1 より大になる。したがって、
\begin{align} ^\exists G, HC(G) &\text{ is True. } \Rightarrow TSP(K_{|V|}) = n \\ ^\exists G, HC(G) &\text{ is False. } \Rightarrow TSP(K_{|V|}) > cn + (n-1) > cn \\ &\quad \text{where $K_{|V|}$ is produced from $G$.} \end{align}
ただし、 はグラフ
の巡回路の重みの総和の最小値を表すとする。
TSP の多項式時間定数近似アルゴリズムが存在しないことの証明
- 前提：判定版 HC が多項式時間で解くことができない（
）
この前提のもとで、証明する。
始めに、判定版 HC 問題の入力として与えられる任意のグラフ について、先ほど述べたような方法で
のエッジに全て重み 1 を導入した上で、さらに
を生成できる。それらについて以下が成り立つことは一つ前のセクションでで確認した通りである。
\begin{align} ^\exists G, HC(G) \text{ is True. } \Rightarrow TSP(K_{|V|}) = n \\ ^\exists G, HC(G) \text{ is False. } \Rightarrow TSP(K_{|V|}) > cn \\ \end{align}
この事実を利用して、背理法を行う。帰無仮説を次のように定義する。
このとき、その について、以下が成り立つことは明らか。すなわち、
\begin{align} ^\exists G, HC(G) \text{ is True. } \Rightarrow TSP(K_{|V|}) = n \Rightarrow ALG(G) \leq cn \\ ^\exists G, HC(G) \text{ is False. } \Rightarrow TSP(K_{|V|}) > cn \Rightarrow ALG(G) > cn \end{align}
これは逆も成り立つ。以下が証明。
のとき
より TSP(G) < cn となる。
が取りうる値は {
以上の数
} なので、
のとき、自明に G はハミルトン閉路ももつ。つまり、
is True:
のとき
より、
のとき、G がハミルトン閉路を持たないのは自明。つまり、
is False.
まとめると次のようになる。
\begin{align} ALG(G) \leq cn \Rightarrow HC(G) \text{ is True.}\\ ALG(G) > cn \Rightarrow HC(G) \text{ is False.} \end{align}
このことは矛盾を孕んでいる。この式は と
の大小関係を比較することによって、G がハミルトン閉路を持つかどうかがわかるということを意味する。
は多項式時間アルゴリズムであることにも注目すると、判定版 HC 問題が多項式時間で解けてしまっていることになり、前提に矛盾する。（判定版 HC は NP 完全問題なので、
に矛盾する。と同義。）
したがって、 の仮定のもとで、TSP の多項式時間定数近似アルゴリズムは存在しないことが証明された。
以上。
証明を終えて
What an elegant proof!
これが初めてこの証明を理解した時の感想である。いやいや、綺麗すぎる。
TSP の多項式時間近似アルゴリズムの存在と に深い関係があることを実感した。非常に面白い。これ、テストに出るかなぁ。
メッセージ
計算量理論は非常に面白い。計算量理論は、我々が難しい問題に直面した時、その問題が難しいということを評価する方法としての役割を担っている。個人の能力が低いからではなく、客観的に、対象としている問題が非常に難しいのだということを説明する力は、分業化が進み個人の能力差の大きく開いた現代において、重要なリベラルアーツではないだろうか。問題が圧倒的に難しいのに、個人の能力のせいだと考え、病んでしまう人もいるのではないだろうか。そういった、「問題の難しさの評価」という観点は理解しやすいし、重要性が分かりやすくはっきりしており、初学者のとっかかりには良いのではないだろうか。かく言う私も、初学者ではあるのだが。
