今回は第1～3回と話題が変わって、計算量、特にPとNP、およびNP完全/困難性、の解説です。 計算量については、yes/noで答えが与えられる問題のクラスにおいて、 入力のサイズの多項式のステップで計算できる問題のクラスがP、 NPは答えがyesである場合にその証拠として多項式時間で確認できるものを与えることができる問題のクラス、 NP完全問題はNPの問題で、NPのクラスの任意の問題を帰着できるもの、というような説明を 一通りしました。 NPと対になるco-NPの話も加え、NPとco-NPの関係、NPとco-NPの交わりにPが入る、というようなことにも 触れています。
この計算量についての話の導入として、タイトルに書いた「グラフのON/OFFゲーム」の話を書きました。 これは特に有名な問題ではなく、「ON/OFFゲーム」という名称もこの記事のために適当につけた名称に過ぎない、 というものでした。しばらく前に高校生向けの体験授業の題材に整理したものを思い付きで紹介しました。 ただ、記事にも書きましたが、調べてみると「σ+ゲーム」という名前で知られているもので あるようでした。
これはどういうゲームかというと、与えられたグラフの各頂点にランプがあり、 いずれか1つのランプに触れるとそのランプおよびそれに隣接する頂点上のランプのON/OFFが反転する、というルールで、 最初に各ランプのON/OFFが任意に与えられているとして、いくつかのランプに順に触れていくことによって すべてのランプをOFFにできるか？ というものです。 下の図は、小さい矢印の示すランプに触れることでどのように状態が変わっていくかを例示しています。
この問題は次のように順に考えるとだいぶ整理されます。
特に、同じランプの触れ方を2度繰り返すと元の状態に戻るので、問題を逆向きに、 すべてのランプがOFFの状態から始めて任意の状態を実現できるか？ と考えても等価な問題ということになります。 以降この方向で考えましょう。
まず、答えがyesの場合、任意の状態を実現するランプの触れ方があるので、特に $i$番目の頂点のランプのみがONで残りがOFFという状態が作れるはずです。 そして、これを重ね合わせると、任意の状態を実現することもできます。 ということは、すべての状態を実現できることを確認する代わりに、$i$番目の頂点のランプのみがON という状態を各頂点に対して実現することだけ確認すれば十分ということになります。
一方、次のような観察もできます。
つまり、答えがyesの場合にもnoの場合にも、それぞれそれを証明する（比較的）簡単な証拠の与え方がある、という形になっています。 これは計算量クラスとして、この問題は NP∩co-NP のクラスに入ることが示せる、ということにつながります。
また、より分かりやすい具体例として、グラフがサイクルグラフの場合には、ここから少し考えると簡単な特徴付けに到達できます。 （サイクルグラフの場合は、頂点数$n$が3で割り切れない場合はyes、3の倍数のときはno、という結論になります。）
…ということなのですが、実は、この問題、（上の方の諸考察から）GF(2)上の線形代数の言葉で記述することにより、 この問題のyes/noの判定は線形写像が全単射かどうかの判定ということになって、そこから一般のグラフに対しても 効率よく判定できることが分かり、計算量クラスとしてはPに入ることがすぐに分かってしまいます。
P,NP等に関する理論は、P≠NP問題が未解決であることを始め、いろいろ未解決な問題だらけなのですが、 一般に、NP∩co-NP の問題はNP-完全にはならないことが信じられていて、ある問題が NP∩co-NP であることが分かれば、 それじゃぁその問題は P なのかも！ という感じになります。このON/OFF問題の場合は実際に P であることも分かるよ、 という例になるわけです。 このON/OFF問題は実際にはここで紹介したようなまどろっこしいことを考える前に、ただちに線形代数の問題として捉えて 結論に至ってしまう人の方が多いかもしれないので、よい例題だったかは微妙なところですが。
先述している、このON/OFF問題を題材にした高校生向けの授業では、(NPやco-NPという話はおいておいて) yesの示し方と noの示し方を具体例で一緒に考えながら提示して、サイクルグラフの場合の答えを解説した上で、演習問題としてパスグラフ の場合にグループワークで取り組んでもらいました。（パスグラフの場合もサイクルグラフの場合と似たような感じの結論になります。） その際に、（高校生相手なので）詳細は省くけれどこの問題は実は線形代数の言葉で考えるときれいに記述できるんだよ、 というお話を軽く加えました。というのは、このときの高校生向け授業は、線形代数はどういうものかを伝える、というテーマで 数名で授業をする中の1コマだったからでした。その意味ではちょうどおあつらえ向きの問題だったのでした。
この回の記事は、最後に、第3回の話と絡め、マトロイドにうまく符号をつけて有向マトロイドにできるかどうか、という 問題がNP-完全ということが示されている、というお話でしめくくっています。 その際に、問題がNP-完全（もしくはNP-困難）ということを調べる研究上の意義として、実際にコンピュータ上で計算プログラムを 効率よく書けるかを知りたいということの他に、問題の複雑さを知ることで、きれいな特徴付けが可能かどうかということの 傍証になるという役割がある、ということを書きました。 これは、この連載の中で書きたかったことの1つでした。
この回の内容は、最後に触れたマトロイドの話で第3回とつながり、また、この後の第5回や第10回でも計算量について触れる機会があり、 連載全体の中では重要なトピックの紹介の回という位置づけのある内容なのですが、 連載12回を終わったあとから眺めなおしてみると、よく見ると実はこの第4回が唯一、幾何学的もしくはトポロジー的な ことに言及しない話題の回になっているのでした。
八森正泰