「どんな地図も、隣り合う地域が同じ色にならないよう塗り分けるには、4色あれば足りる」——これが四色定理です。1852年に予想され、証明されたのは1976年。しかもその証明は、1900種類近い配置をコンピュータでしらみつぶしに確認するという、当時としては前代未聞のやり方でした。「人間が読んで納得できない証明は、証明と呼べるのか」という論争を巻き起こしたことでも知られています。
今回、国立情報学研究所や東京大学などの国際チームが、その証明の手続きそのものを大きく速くする新しいアプローチを発表しました。1997年の簡潔化以来、約30年ぶりの刷新だといいます。
証明とは、ある主張が例外なく成り立つことを、疑いようのない形で示す営みです。四色定理の証明は「起こりうる配置を全部洗い出し、どれも4色で塗れると確認する」というやり方を取ります。従来はこの配置を1つずつ順番に調べていましたが、新しいアプローチは、互いに干渉しない配置をまとめて処理できる仕組みを見つけました。地図の中でも従来あまり使われていなかった「平らな領域」に着目し、8202種類という大規模な配置集合を発見したのです。
その結果、必要な手間(計算量)は、これまでのO(n²)程度からO(n log n)へと大きく改善されました。同じ結論にたどり着くにも、手順しだいで手間が桁違いに変わる——この「計算量」という視点は、四色定理に限らず、AIの学習からデータベースの検索まで、あらゆる計算の裏側で効いている考え方です。派手な結論の陰にある「どれだけ速く、確実に証明できるか」という地道な改良にも、目を向けてみる価値があります。