計算量

2026年9月16日

地図を4色で塗り分けられる証明に、約30年ぶりの新アプローチ——鍵は「同時に処理する」発想

国立情報学研究所や東京大学などの国際共同研究チームが、隣り合う地域を4色で塗り分けられることを 示す「四色定理」に新しい証明アプローチを発表した。1997年の簡潔化以来、約30年ぶりの手法刷新とされる。 配置を1つずつ調べていた従来の手順に対し、互いに干渉しない配置をまとめて処理する仕組みにより、 計算量をO(n²)程度からO(n log n)へ大幅に改善したという。