『４色問題③』

締切済

質問者：wonderlasting
質問日時：2022/11/14 00:31
回答数：2件

正確には４色問題とはいい難いかもしれませんが、４色問題も関係なしとは言えないし、大目に見てください。実は、３彩色問題にP-NP問題が絡む疑問なのです。長くなりますが、ご容赦ください。
3彩色問題とは、御存知でしょうが、任意の地図で隣り合う国を異なる色にする条件で塗り分けるのに3色で足りるか判定せよ、という問題で、NP完全問題として知られています。
いま、ある地図が与えられ３色塗り分けが可能か判定せよ、とされたとします。そこで、ある方法、例えば、全ての２次元平面に描かれた地図は千数百か数百の基本パターンの組み合わせによって作られる（正確には不可避集合と呼ぶべきかもしれませんがここでは基本パターンとよぶことにします）ことを利用して、そのパターン群中、塗り分けに３色で足りるパターンを抽出しておき、それが与えられた地図の中にあるか検出して、３色で足りるか４色必要かを判定するとします。これには、結構な時間がかかるかもしれませんが、うまくいけば国の数＝nとして、コンピュータの処理ステップ数に換算してn²∼³に比例する手間で判定でき（るかもしれず）たとすると、NP完全問題が一つ、多項式時間で解けたことになる。NP完全問題の性質として、一問でも多項式時間で解ければ、他のNP完全問題も多項式時間で解けることになり、つまりはP＝NPということになります。
が、そううまくはいかないでしょう。何故か？
上記の方法で判定結果そのものは正解だったとしても、たまたま与えられた地図が多項式時間で解ける問題、つまりP問題ともいうべきか、だったから、言い換えると、３彩色問題すべてがNP完全問題とは限らず、中にはP問題もあるだろうからです。
そこで疑問は、３彩色問題で、PかNP完全かをどうやって見分ければよいのか、その方法は？ということなのです。（もしかすると、この見分け自体、NP問題なのかも？）