If a million computer scientists had dinner together, they would get a huge bill. If one of them is particularly frugal and wants to check that the bill is correct, the verification process is simple but tedious: they have to check the bill, adding up all the individual prices line by line, making sure the total equals the total bill. But in 1992, six computer scientists demonstrated in two papers that a radical shortcut could be taken. There is always a way to reformat a bill of arbitrary length that can be checked with just a few queries. What’s more, they found that this is true of any calculation, or even any mathematical proof, because both have their own receipts: a record of the steps that either the computer or the mathematician must take.
This very compact format is called a Probabilistically Checkable Proof (PCP) . PCP has become one of the most important tools in theoretical computer science. They have even found their way into practical applications recently, such as being used in cryptocurrencies to aggregate large batches of transactions into smaller forms that are easier to verify. Before the creation of PCP, computer scientists had identified a whole class of problems with solutions akin to checking the dinner bill—if you had a solution, it was easy to verify. But for many of these problems, the time it takes to find a solution first seems impractical.
Computer scientists name these kinds of hard-to-solve but efficiently verifiable problems NP. It provides a conceptual home for many of the practical problems we care about as well as more abstract ones such as finding proofs for mathematical theorems. Solving is a step-by-step process of finding a mathematical conclusion with absolute certainty—like summing up a bill to prove the total. Solving can be difficult, but once you have a solution, it’s straightforward to check. Such proofs fall entirely within the category of NP .
This article is reprinted from: https://www.solidot.org/story?sid=71614
This site is for inclusion only, and the copyright belongs to the original author.