四色定理に約30年ぶりの新証明、地図を4色で塗り分けるアルゴリズムが大幅に高速化

どんな地図でも隣り合う地域を同じ色にしないように4色だけで塗り分けられるという「四色定理」について、日本やデンマークなどの研究者からなるチームが新たな証明を発表しました。今回もコンピューターを利用した証明ですが、従来とは異なる場所に着目することで、多数の処理をまとめて行えるようになり、実際にグラフを4色で塗り分けるアルゴリズムも大幅に高速化されていると、科学系メディアのQuanta Magazineが解説しています。 [2603.24880] The Four Color Theorem with Linearly Many Reducible Configurations and Near-Linear Time Coloring https://arxiv.org/abs/2603.24880 The Four-Color Theorem Gets a Rare New Proof |

[LM-7]

アルゴリズムを改良してO(𝑛²)からO(𝑛log𝑛)になったという話だった

[hiro_curry]

「AIが数学の難問を解決していいのか」に対する一つのアンサーになってそう。コンピュータが問題を解く過程においても便利な道具は生まれるんだね

[arajin]

「各頂点が6つの頂点につながり三角形が規則的に並ぶような、これまであまり利用されてこなかった「平らな領域」にまで探索対象を広げ」「4色で塗り分けるための計算量は従来のO(n2)からO(nlog_n)へと改善」

[igni3]

なんかよくわからなくて3回くらい読んでしまったが、証明は面倒くさくなったけど、実際に塗り分けるアルゴリズムは速くなるという話か

[natu3kan]

どんどん開拓されるな四色定理とタイル張り系の問題は

[nguyen-oi]

計算量がO(n^2)からO(n log n)に落ちたのは胸熱。数理アルゴリズムの進歩すげーな