Imagine that you have a book of puzzles. After working on a particularly tough puzzle, you decide to look in the back of the book for the answer.
What you find in the back of the book should clearly be a solution to the puzzle. It should not be so hard to see that it works that it is just as hard as the original puzzle!
The point here is that there is a big difference between finding a solution to a puzzle and checking a solution that was found by someone else.
A nondeterministic algorithm is an evidence checker.
Suppose that L is a language. An evidence checker, also called a verifier, for L is a program p(x, e) that has the following properties.
(The algorithm must be reasonable.) If x ∈ L then there exists a value e so that p(x, e) = true.
(The algorithm must not be gullible.) If x ∉ L then for every e, p(x, e) = false.
The idea is that someone else helps you by providing evidence e. You only need to check whether the evidence is convincing.
Long ago, a mathematician named Mersenne made a conjecture.
Mersenne's conjecture If p is a prime number then 2p−1 is also a prime number.
For example, 22−1 = 3, 23−1 = 7, 25−1 = 31, and all of those numbers are prime.
But Mersenne could not check his conjecture for very many values of p because of the cost of checking primality by hand.
In about 1900, another mathematician, Frank Cole, wanted to prove that Mersenne's conjecture is false.
Since 67 is a prime number, Mersenne's conjecture says that 267−1 is prime. Cole worked for what he described as "three years of Sundays" trying to find a nontrivial factor of 267−1. Finally, he succeeded.
In 1903, Cole presented his proof of the falseness of Mersenne's conjecture at a mathematical meeting. By successive doubling and finally subtracting 1, he computed 267−1. Then he wrote down two numbers and multiplied them together.
The result of the multiplication was exactly the same as 267−1.
Cole had to find a factor of 267−1 deterministically. That took a lot of time.
The people in the audience at his presentation only needed to check his result. They did not need to find the factors of 267−1. It took roughly half an hour.
But the audience did need to pay attention and check that Cole's proof was correct. What do you think would have happened if Cole had simply said "Mersenne's conjecture is false; trust me."