Computer-assisted proof — Safekipedia Discoverer

A computer-assisted proof is a mathematical proof that has been at least partially generated by computer. This means that mathematicians use computers to help check or create proofs for really tough math problems.

Most computer-aided proofs are done by trying out every single possibility, a method called proofs-by-exhaustion. For example, a computer can carefully check millions or even billions of cases to show that a math idea is always true. A famous example is the four color theorem, which was the first big math idea proven with the help of a computer program in 1976. This theorem explains that any map can be colored using just four colors so that no two neighboring areas share the same color.

Researchers in artificial intelligence are also working on ways to let computers find new proofs on their own. They use special techniques called automated reasoning, including heuristic search, to help computers discover and prove new math ideas. These tools, known as automated theorem provers, have found new results and fresh proofs for old theorems.

There are also tools called interactive proof assistants that help mathematicians write proofs that are easy to read but also checked by a computer for mistakes. These proofs can be looked at by people, though they might be hard to follow, like the proof of the Robbins conjecture. These methods are less controversial than the exhaustive checking done by computers because they keep the proofs understandable to humans.

Methods

One way to use computers for mathematical proofs is through a method called validated numerics. This means doing calculations with numbers very carefully, making sure that the results are completely accurate. We do this by using special math rules that keep track of tiny errors that can happen when a computer rounds numbers.

We break down problems into simple steps, like adding, subtracting, multiplying, and dividing. For each step, we don’t just use a single number. Instead, we use a range — an interval — that we know the real answer must fall inside. By carefully moving from one interval to the next, we can be certain that our final answer is correct.

Philosophical objections

Main article: Non-surveyable proof

Some people think that computer-assisted proofs are not truly "real" proofs because they have so many steps that humans cannot check them all. They worry that we might just be trusting a computer instead of using our own reasoning.

Others suggest that these proofs are more like calculations. They say we can make the computer programs used in proofs correct by testing them carefully. This way, we can trust the results more. However, some still feel that these proofs lack the beauty and insight that mathematicians usually enjoy. They also wonder if using computers too much changes what mathematics really means, turning it more into a type of science that relies on experiments rather than pure thinking.

Theorems proved with the help of computer programs

See also: Proof assistant § Notable formalized proofs

This list includes important math problems that were solved using computer programs. These programs helped check huge amounts of information to support the solutions.

Common fixed point problem, 1967
Four color theorem, 1976
Mitchell Feigenbaum's universality conjecture in non-linear dynamics. Proven by O. E. Lanford using rigorous computer arithmetic, 1982
Connect Four, 1988 – a solved game
Non-existence of a finite projective plane of order 10, 1989
Double bubble conjecture, 1995
Robbins conjecture, 1996
Kepler conjecture, 1998 – the problem of optimal sphere packing in a box
Lorenz attractor, 2002 – 14th of Smale's problems proved by Warwick Tucker using interval arithmetic
17-point case of the Happy Ending problem, 2006
Kouril (between 2006 and 2016) computed several van der Waerden numbers using FPGA-based SAT-solver.
NP-hardness of minimum-weight triangulation, 2008
Ahmed (between 2009 and 2014) computed several van der Waerden numbers using DPLL algorithm-based stand-alone and distributed SAT-solvers. Ahmed first used cluster-distributed SAT-solvers to prove w(2; 3, 17) = 279 and w(2; 3, 18) = 312 in 2010.
Optimal solutions for Rubik's Cube can be obtained in at most 20 face moves, 2010
Minimum number of clues for a solvable Sudoku puzzle is 17, 2012
In 2014 a special case of the Erdős discrepancy problem was solved using a SAT-solver. The full conjecture was later solved by Terence Tao without computer assistance.
Boolean Pythagorean triples problem solved using 200 terabytes of data in May 2016.
Applications to the Kolmogorov-Arnold-Moser theory
Kazhdan's property (T) for the automorphism group of a free group of rank at least five
Schur number five, the proof that S(5) = 161 was announced in 2017 by Marijn Heule and took up 2 petabytes of space
Keller's conjecture in dimension 7 the only remaining case in 2020 with a 200 gigabyte proof
The packing chromatic number of the infinite square grid is 15, by Subercaseaux and Heule in 2023 (See also: Hadwiger–Nelson problem for the chromatic number of the plane)