『４色問題⓶』

PNP問題というミレニアム問題があります。世の中にはNP問題が溢れているということですが、４色問題、即ち、「与えられた地図上の隣接する国を異なる色に塗り分けよ、ただし４色以内で」という問題というか課題はどうなのでしょうか？この課題を実行するのにP時間＝多項式時間（コンピュータでやるとするならステップ数となりましょうが）で済むのか、それ以上かかるのか？

No.3 回答者： Tacosan 回答日時： 2022/11/02 18:37

ちょいと調べてみたけど「証明」が正しければ O(n^2) 時間 (n は「国」の数) でいいみたい.

「3色で塗れるグラフを 3色で塗ってみろ」は NP 完全だったかな?

この回答へのお礼

ありがとうございます。

お礼日時：2022/11/03 11:43

No.2 回答者： ありものがたり 回答日時： 2022/10/31 22:42

考え直してみました。

地図の四色塗り分けを見つけるときに、時間がかかるのは、
色を塗り替える時間よりも、不可避集合の中のどのパターンが
地図のどこにあてはまるのかを検索する作業かと思います。
それにどの程度の時間がかかるのかは、地図やパターンを保管する
データ構造とか検索アルゴリズムとかに依存するでしょうが、
ナイーブに片っ端から突合していったとすると、地図が n 国
不可避集合中の最大のパターンが p 国からなるとして
nCp に比例する時間がかかってしまいます。
No.1 に書いた評価よりはかなり多い計算量になりますが、
まあそれでも多項式時間であることにはかわりありません。

この回答へのお礼

ありがとうございます。

お礼日時：2022/11/01 12:18

No.1 回答者： ありものがたり 回答日時： 2022/10/31 13:39

四色問題自体は、既に証明が完成しているので有限時間です。

数学的帰納法を含むけれど、帰納法というのは
実際に帰納を行わなくても帰納できることが判る
という論法ですからね。証明の長さは国数に依存しません。
定数時間なので多項式時間に含まれます。

証明ではなくて、与えられた n 国地図の四色塗り分けを
見つける時間のことを言っているのだとしても、多項式時間です。
アッペル・ハーケンのアルゴリズムは、次の国を塗るために
既に塗った国を塗り変える場合がありますが、
塗った所を無かったことにしてやり直すわけではなく
塗り替えが済んだら予定通り次の国が塗れるので、
バックトラックは生じません。
最悪見積もりで、一国塗る度にほぼ毎回、それまで塗った国を
ほぼ全て塗り替えるとしても、色を塗る回数は ∑[k=1..n]k
で見積もることができ、アルゴリズムは多項式時間(二次式)です。