多項式時間で計算可能なハミルトン閉路問題の解法についての提唱(P=NPの証明)
- S Y
- 2022年9月15日
- 読了時間: 5分
0.参考文献
[5] 「線形代数学 初歩からジョルダン標準形へ」三宅敏恒
1.ハミルトン閉路問題[1]
ハミルトン閉路問題は、以下の問題のことです。
「あるグラフGに対して、全ての頂点を1度だけ通って初めの頂点に戻れるような閉路を求めよ」
以下の例があります。
これの解は次の通りです。
今までは一般に、総当たりの方法、あるいはそれに近いダイアグラムを作成する方法が提案されてきました。しかし、いずれのプログラムも計算時間は指数時間となってしまう問題がありました。つまり、「P問題に属するかもしれないが、属する証拠(=プログラム)がまだ見つかっていない。あるいは、本当は証拠が存在しないのかもしれない」と考えられていました。
一方、この問題は明らかにNP問題です。解の正しさを多項式時間で判定することができます。
特にハミルトン閉路問題は、「NP問題に属するすべての問題を、多項式時間で帰着可能」なNP完全問題です。
「帰着可能」とは、「見方を変えれば同じことだ」という意味です。
つまり、ハミルトン閉路問題に対して、多項式時間で解く方法(アルゴリズム、プログラム)があれば、P=NPを証明することができます。
2.エントロピー行列Sの上三角行列Σ、及び下三角行列(t^)Σの、グラフ理論における応用[2][3]
グラフ理論において、その性質を示す方法に隣接行列があります。
無向グラフ
以下の例を挙げます。
この時、以下の行列を与えることができます。
頂点が互いに接続している場合は、1を、そうでない場合は0を記入していきます。ところが、エントロピー行列で考えていたように、n*(n+1)成分、及び(n+1)*n行列が1に必ずしもなってはいません。そこで、次のように順番を入れ替えます。(1以外の空白部分は0ですが、以下、省略しました)
このようにした後、エントロピー行列に近づけるために、一旦対称性を踏まえて以下のように考えます。
上三角行列となります。
これに対して、ガウスの消去法を考えます。すると、逆行列がもとまり、次のようになりました。
この逆行列の本質は、一次独立なベクトルが2つ存在して、他のベクトルはその一次従属の関係にあることがわかることです。
言い換えると、2次平面の閉路(=円)を生成する条件のベクトル2つを定めることができ、すなわち、ハミルトン閉路を見つけることができることを意味しています。
例えば、今回はB,C,F,Eについて、Dの一次従属であることがわかりますので、D→E→F→C→Bの経路が定まります。(成分a_(mn)において、nの大きい方が次元が高く、優先的であるとすれば、隣接性を保証できます)。
一方、Aについて、Dの一次従属であることがわかりますので、A→Dの経路が定まります。(Eに対しても従属ですが、より高い次元を持つDの方を優先させました。
最後に、一次独立なGのベクトルを考えます。これは、閉路にするために複数の経路を繋げることと同じです。
結果的に、A→D→E→F→C→B→G→Aという閉路を考えることができました。
3.有向ハミルトン閉路の解法
2と同じです。ただし、行列について注意することとして、接続していても向きが誤っている場合(例えば、A→Bはあって、B→Aはない、B→Aの場合。ただし、A,Bは頂点)については、1ではなく、0とします。
これにより、エントロピー行列は対称行列ではなくなります。この場合は、上三角行列と下三角行列のそれぞれについて、2の解法を用いる必要があり、それぞれで作った経路をまとめて、閉路を作ることで解けます。
4.行列Σへ変換する過程で得られる逆行列は、何を表しているか？また、オーレの定理は何を言っていたか？[4]
2章で、逆行列を求めることにより、一次独立性及び一次従属性を調べることにより、閉路探索ができました。
結果的に、一次独立なベクトルが2つあり、他のベクトルはすべて一次従属であることを示しました。ところで、閉路=円についての方程式において、その自由度は、2つですから(x^2+y^2=r^2, r=const.)、その空間には閉路が存在すること、及び閉路それ自体がわかります。
ところで、ハミルトン閉路が存在することの十分条件として、オーレの定理というものがあります。隣接しない頂点どうしの、次数の和がいつでもグラフの頂点の数以上であれば、必ずハミルトン閉路が存在することを意味しています。
今回の行列の言葉で言えば、以下の定理こそ、オーレの定理を言っていることに気づきます。
Tはベクトル空間Vの線形変換とし、Tの相異なる固有値をλ_iとすれば、以下を満たす
ここに、グラフ理論にける互いに独立な固有ベクトルの次元は、隣接しない頂点の次数を意味しています。また、グラフの辺の数が系の次元を意味しているので、dim(V)に相当します。
5.ハミルトン閉路が存在しないとはどういうことか？
実際に計算した結果、一次独立なベクトルが3つ以上ある場合です。あるいは、一次独立なベクトルが1つ以下であることです。1つの時は半ハミルトン閉路の存在性を意味しています。
6.ハミルトン閉路問題がNP完全問題として、指数時間かかると思われていた要因と、なぜこの解法がクラスPに相当するかの説明
ハミルトン閉路問題がNP完全問題として、指数時間かかると思われていた要因はなぜでしょうか？
ところが、今回の方法は、各ベクトルに対する一次独立性及び一次従属性の決定によるので、行列のサイズnた。その計算過程で、n^2行列に対して、0と1の変換を一度にm個計算することができました。しかし、今までは各成分に対して、0か1のどっちを取るかを(ある意味で)前通り考える必要があったので、2^(n^2)だけ計算する必要があったのです。
ところが、今回の方法は、各ベクトルに対する一次独立性及び一次従属性の決定によるので、n次正方行列に対して、高々(n+(n^2+n)/2)で解を与えることができます。
明らかに多項式時間となっています。
よって、このアルゴリズムは、多項式時間で計算可能となります。
結論、ハミルトン閉路問題はNP完全問題であり、かつP問題ですので、P=NPであることを示せました。
(追記)[6]
オーレの定理に従わずにハミルトン閉路ができるグラフが参考文献に紹介されていました。グラフの行列は次のようになります。
頂点は以下のようにふります
この時、行列は次のようになります。
以下のようにエントロピー行列ごとにグループ分けできます。
以上から、[A~E]と[F~G]についての絡み合い方について、対称であることがわかりますので、解が存在することがわかります。(つまり、A~Eについての回転と、F~Jについての回転を考えた後、2つの回転を合成することが可能であることが対称性よりわかる、ということです。)
E→Cがわかるのでこれを接続する経路C→I→Eを確定させることができます。J→Gがわかるので、J→A→Gが、J→Hがわかるので、H→B→A→Jがわかります。
以上から、オーレの定理よりも容易に、解が存在すること(対称性)及び、解法がわかりました。
Commentaires