計算機援用証明

計算機援用証明とは、コンピュータによって少なくとも一部が生成された数学的証明である。今日における計算機援用証明のほとんどは数学的定理に対するしらみつぶし法の実装である。具体的には、膨大で複雑な計算をコンピュータによって実行し、計算結果が与えられた定理の主張を裏付けることを示す試みである。1976年に示された四色定理が計算機援用証明によって示された最初の定理である。計算機援用証明は人工知能の分野でも使われ、簡明かつ陽的で新しい（数学の）定理の証明を作り出すことが目指された。このような自動定理証明機はいくつかの新しい結果を生み出し、既存の定理に対しても新しい証明を発見した。

手法

数学的証明の中でコンピュータを用いる方法の一つとして精度保証付き数値計算が挙げられる。これは数学的厳密さを保持したうえで数値計算を行うことを意味する。数値的プログラムの出力が与えられた数学的問題の解を含むことを示すために集合値演算などを使用する。これは区間演算などによって丸め誤差と打切り誤差を包含、伝播させることでなされる。より具体的には、数値計算を四則演算に簡略化する。計算機では四則演算の結果は計算精度に応じて丸められる。だが、四則演算の結果に関する上界と下界を与える区間を作ることができる。そして数を区間に置き換え、四則演算を計算機で表現可能な数で構成した区間で行う。

計算機援用証明で示された定理

四色定理
ケプラー予想
Double bubble 予想
Wright 予想
14番目のスメイルの問題、ウォリック・タッカーによって区間演算を使って解決された。
Robbins 予想
Connect Four
ブールピタゴラス数問題

出典

参考文献

Nakao, Mitsuhiro T; Plum, Michael; Watanabe, Yoshitaka (2019). Numerical verification methods and computer-assisted proofs for partial differential equations. Springer. doi:10.1007/978-981-13-7669-6. https://link.springer.com/book/10.1007/978-981-13-7669-6
Meyer, K. R., & Schmidt, D. S. (Eds.). (2012). Computer aided proofs in analysis. en:Springer Science & Business Media.
Lanford, O. E. (1992). Computer assisted proofs. In Computational Methods in Field Theory (pp. 43-58). Springer, Berlin, Heidelberg.