NP完全問題の問いです。

質問

３彩色問題はNP完全問題なのに、何故、四色問題はNP完全問題ではないのでしょうか。矛盾していませんでしょうか。

回答No.2

mitoneko · ベストアンサー

全然矛盾してないと思いますよ。
　数学の問題は、有る一カ所の数字がほんの少し変わっただけで、あっという間に真偽が変わり、証明がむやみやたらと困難になる分野でもあります。
　しかも、数が多い方がかえって簡単な問題だったりするからたちが悪いですね。
　フェルマーの最終定理のn（乗数）ごとの個別証明がされた順番なんか、なかなか興味深いです。必ずしも、数字順に証明されていないんですね。確か、４乗の次が３乗で、次は、１４と７乗かな。（フェルマーの最終定理（フェルマー・ワイルズの定理）：x^n+y^n=z^n(n>2の自然数)を満たす自然数(x,y,z)の組は存在しない。）
　数字が大きい方が一概に難しいというものでもないと。その数字に独特の何かの性質が解決の糸筋になったりしますから。

　ＮＰ完全であることの定義では、主に二つのことを求めます。
　１．解を求めるためには、全てのパターンをランダムにしらみつぶしに探していくほか無い。
　２．解の候補を作るのにＯ（１）、その解が正しいかどうかを検証するのに、Ｏ（ｎ＾ｋ）の計算量が必要になる。

　さて、四色問題は、不可避集合を求めれば、事実上解けますし、つまり、不可避集合の大きさが、オーダーの限界値として存在することになります。（１．を満たさない。）
　事実、四色問題の証明は、この集合をしらみつぶしにすることで証明されていたと記憶しています。

　三彩色問題でも、このような集合が有れば良いですが、残念ながら無いようですね。

　四色問題の反例は、もしかして、ガードナーのエイプリルフールかしら？（Scientific Americanの1975/4月号でSix Sensational Discoveries（世間を驚かせた６つの発見）に掲載されたマクレガーの地図　http://torito.jp/puzzles/126.shtml）

お礼

御回答を誠に有難う御座いました。

回答No.1

simotani

四色問題は数学的に四色で塗れない問題を作図する事が1例だけ可能な事が示された筈ですが?
これはコンピューターの発達によりこれまで作図不可能と証明された事をひっくり返した事になります。一般論としては地図は山岳の稜線や湖水水面上に線引きされる事が通例であり、確かにこうした実務的な作図には四色問題の結論は有効です。
が、規定を掻い潜る為にプログラムされた作図についてだけは勝てない証明がされたのです。

お礼

お世話様でした。

補足

ウィキペディアその他にも、その様な「反例」など書いてありませんが。