Computer-assisted proof — Safekipedia Adventurer

A computer-assisted proof is a mathematical proof that has been helped by a computer. Mathematicians use computers to check or create proofs for very difficult math problems.

Most computer-aided proofs work by trying out every single possibility, a method called proofs-by-exhaustion. For example, a computer can 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 shows 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 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 read by people, though they might be hard to follow, like the proof of the Robbins conjecture.

Methods

One way to use computers for mathematical proofs is through a method called validated numerics. This means doing calculations with numbers very carefully. We make sure the results are always accurate.

We do this by using special math rules. These rules watch for tiny errors that can happen when a computer rounds numbers.

We break down problems into simple steps. These steps include adding, subtracting, multiplying, and dividing. For each step, we don’t just use one number. Instead, we use a range. This range shows where the real answer must be. By moving from one range to the next, we can be sure our final answer is correct.

Philosophical objections

Main article: Non-surveyable proof

Some people think that computer-assisted proofs are not truly "real" proofs. They say this is because these proofs 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 thinking.

Others say these proofs are more like calculations. They believe we can make the computer programs used in proofs correct by testing them carefully. This way, we can trust the results better. 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.

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.
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.
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
Keller's conjecture in dimension 7 the only remaining case in 2020
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)