Blog – Page 1757

Everybody involved has long known that some math problems are too hard to solve (at least without unlimited time), but a proposed solution could be rather easily verified. Suppose someone claims to have the answer to such a very hard problem. Their proof is much too long to check line by line. Can you verify the answer merely by asking that person (the “prover”) some questions? Sometimes, yes. But for very complicated proofs, probably not. If there are two provers, though, both in possession of the proof, asking each of them some questions might allow you to verify that the proof is correct (at least with very high probability). There’s a catch, though — the provers must be kept separate, so they can’t communicate and therefore collude on how to answer your questions. (This approach is called MIP, for multiprover interactive proof.)

Verifying a proof without actually seeing it is not that strange a concept. Many examples exist for how a prover can convince you that they know the answer to a problem without actually telling you the answer. A standard method for coding secret messages, for example, relies on using a very large number (perhaps hundreds of digits long) to encode the message. It can be decoded only by someone who knows the prime factors that, when multiplied together, produce the very large number. It’s impossible to figure out those prime numbers (within the lifetime of the universe) even with an army of supercomputers. So if someone can decode your message, they’ve proved to you that they know the primes, without needing to tell you what they are.