NP completeは現実世界では問題ない程度に満足解を作ることができる
立体は4色以上で塗り分け可能である。一方平面は1-4色で塗り分け可能である。3 colorableの判定はNP completeであるものの、現代のコンピューターはNP completeを3-SATに変換してCDCL(conflict driven clause learning)でsatisficingしてしまう。NP completeは数学理論上は宇宙の全資源を持ってしても解けない問題という定義ではあったが現実空間では3-SATのディオファントス方程式に変換してSAT solverのCDCLを繰り返せば解の判定も、解の構築もできるようになった。つまり演算資源はNPの壁を壊した。NVIDIA, TSMC, ASMLに代表される3SAT solverインフラは人類が願望を物質化する工程を人間の力を超えた重機的な力技で実現してしまっているのである。
例えば3色塗り分け問題はNP completeである。
平面グラフ（地図）の3彩色判定が、全数チェックをせずに「一瞬（線形時間）」で終わる具体的なプロセスが発見されている。これは数百年の数学の歴史が必要だったものの、現代のコンピュータはこれを解いてしまう。
平面グラフの3彩色判定アルゴリズム
大まかな方針は外側からタマネギの皮をむくように、グラフをどんどん小さくしていくことです。
[入力] 与えられた平面グラフ G
↓
[ループ開始] 頂点数が「4つ以下」になるまで繰り返す
│
├─ 1. 「3角形（3サイクル）」が1つもない場合
│ ⇒ 【即座に終了】 判定は「3彩色可能（YES）」
│
├─ 2. 「次数が1または2」の頂点 v がある場合
│ ⇒ 【縮約】 頂点 v とそれに繋がる辺をグラフから削除する
│
├─ 3. 「次数が3」の頂点 v がある場合
│ ⇒ 【縮約】 頂点 v を削除し、周囲の3つの頂点同士を辺で結ぶ
│
└─ 4. 「次数が4または5」の頂点がある場合
⇒ 【縮約】 特定の隣接頂点同士を「1つの頂点に合体（収縮）」させる
↓
[ループ終了]
↓
[最終判定] 残った小さなグラフが3色で塗れるなら「YES」、塗れないなら「NO」各プロセスの詳細なメカニズム
ステップ 1：グロッチュの定理による一発判定（ショートカット）
プログラムはまず、グラフの中に「三角形（3つの国が互いに隣り合っている場所）」があるかどうかをスキャンします。
もし三角形が1つもなければ、その時点で計算を終了し、「3彩色可能（YES）」という答えを出力します（グロッチュの定理より、三角形のない平面グラフは100%3色で塗れるため）。
ステップ 2：低次数の頂点の削除
三角形がある場合、次に「つながっている辺が少ない頂点」を探します。オイラーの定理から、平面グラフには必ず次数5以下の頂点が存在するため、以下のいずれかのケースに必ずヒットします。
- 次数1 or 2 の頂点がある場合：
その頂点（国）を一旦グラフから消し去ります。なぜなら、その周りの国が何色に塗られようとも、1〜2色しか使われていないため、3色目（あるいは2色目）を使って後から確実にその国を安全に塗ることができるからです。 - 次数3 の頂点 v がある場合：
v を削除し、 v の周囲にいた3つの頂点 a, b, c を互いに辺で結びます。こうすることで、「 a, b, c はすべて違う色で塗られなければならない」という制約を維持したまま、頂点数を1つ減らすことができます。
ステップ 3：次数4または5の頂点の合体（収縮：Identification）
もしグラフの中に次数3以下の頂点がなくなっても、平面グラフなら必ず次数4または5の頂点が残っています。ここがアルゴリズムの最も賢い部分です。
例えば、4つの国（ a, b, c, d ）に囲まれた国 v （次数4）があるとします。
- 周囲の4つの国のうち、「直接隣り合っていない2つの国（例：a と c）」を選びます。
- 国 v を消去すると同時に、国 a と国 c をギュッと押しつぶして「1つの国（ ac ）」に合体させます。
- これにより、「 a と c は絶対に同じ色になる」という強い制約を持たせた、より小さな新しい平面グラフが完成します。
なぜこのプロセスで「判定」ができるのか？
このは、数学的に「変形する前のグラフが3色で塗れること」と「変形した後のグラフが3色で塗れること」が完全に一致する（等価である）ように設計されています。したがって、頂点数が100万個ある巨大な地図であっても、このルールに従って頂点を1つずつプチプチと消去・合体していくと、最終的には「頂点数がわずか3〜4個の、目で見れば一瞬で3色で塗れるか分かる超ミニマムなグラフ」にまで縮小されます。
- 最後に残ったミニグラフが3色で塗れた ⇒ 元の100万カ国の地図も3彩色可能。
- 最後に残ったミニグラフが3色で塗れなかった ⇒ 元の100万カ国の地図は3彩色不可能（4色必要）。
結論：手戻り（バックトラック）が一切ない
n次元一般グラフの3彩色（NP完全）では、「赤に塗ってみたけどダメだったから、戻って青に塗り直す」という手戻り（バックトラック）が無限に発生します。しかし、この平面グラフの判定プロセスを明示して分かる通り、「頂点を見つける ⇒ 潰す」という操作は常に1方向（片道切符）で進みます。一度潰した頂点に戻ってやり直す必要が一切ありません。頂点数を n としたとき、この「潰す操作」を最大 n 回繰り返すだけで必ず答え（YES/NO）にたどり着くため、プロセス全体が O(n)（線形時間）という文字通りの「一瞬」で終了するのです。
3次元空間や4次元になると3-colorableはより難しくなるものの、手順を踏めばコンピューターで満足解を出す方法はある。
① 線形時間アルゴリズムの出典
- 論文名： Linear-time algorithms for maximum matchings and approximate coloring in planar graphs
- 著者： Magnús M. Halldórsson, S. Sridharan
- 発表年： 1995年
- 概要： 平面グラフにおいて、次数が低い頂点から効率的に処理（収縮や削除）を行うことで、彩色問題やその近似解を O(n)（線形時間）という驚異的な速さで解くアルゴリズムを提案・整理した論文です。
② 「次数5以下を縮約する」というアイデアの歴史的起源
平面グラフを次数5以下の性質（オイラーの公式の帰結）を使って、頂点を合体・削除しながら変形していくアプローチは、有名な「四色定理」の証明プロセスです。
- 論文名： Every Planar Map is Four Colorable
- 著者： Kenneth Appel, Wolfgang Haken（アペルとハーケン）
- 発表年： 1977年
- 概要： 世界で初めてコンピュータを使って「四色定理」を証明した歴史的論文です。この中で彼らは、平面グラフから特定の「避けられない配置（次数5以下の周囲の構造）」を見つけ、それを縮約・変形して判定していくプログラムを組みました。この手法が、のちに「3彩色」を高速判定するアルゴリズムへと応用されました。
ステップ1（三角形がない ➔ 3色で塗れる）の出典
- 定理名： グロッチュの定理（Grötzsch’s theorem）
- 論文名： Zur Theorie der Optimierung von Graphen（ドイツ語）
- 著者： Herbert Grötzsch（ヘルベルト・グロッチュ）
- 発表年： 1959年
- 内容： 「三角形（長さ3の閉路）を持たない平面グラフは、すべて3彩色可能である」ということを証明した定理です。
ステップ2・3（次数5以下の頂点が存在する）の出典
- 定理名： オイラーの多面体定理（Euler’s polyhedron formula） からの系
- 数理的裏付け： すべての平面グラフは、辺の数が頂点の数の3倍未満（ E ≤ 3V – 6 ）になるという性質があります。ここから平均次数が6未満になるため、「平面グラフには必ず次数5以下の頂点が最低1つは存在する」という定理が導かれます。これが、ステップ2と3が「絶対に途中で手詰まり（フリーズ）しない」ことの数学的証明になっています。