Today’s puzzle reveals one of the blockbusters of theoretical computer science. Experts in the field are appalled.
We arrive at the result ( PCP theorem) later. But let’s try the challenge first!
It’s a word puzzle. Each crossword style clue points to a vertical column. The answer to each clue is his 3 letter word made up of the 3 letters the clue points to.
Let’s solve this together. An animal with three letters? What about “bats”?
You earn points for each letter each time you can type a convincing answer. “Bat” has a score of 3.
Let’s continue. One way to complete the grid is as follows.
Please note that this grid is not a complete solution. The top three clues are completely answered. I highlighted the green arrow on the clue “verb” that points to “pay.” However, her last three clues are only partially solved. The food refers to “peas”, not “peas”. However, you can give points for any letter that could be correct, so for “pey” she gets 2 points for her two correct letters in “pea”. Total score: 15 points.
Here’s how to get the complete solution with maximum score of 18. Of course, it’s much more obvious to start with “cat”.
Dana Moszkovitz, a computer science professor at the University of Texas at Austin, said the key to this puzzle is that “it’s okay to get a partial solution.” In fact, it’s fun. The goal is to get the highest score possible.
Here are three examples in order of difficulty.
Question 1
Problem 2
Problem 3
We’ll be back at 5pm UK with the full solution. (There are probably many perfect solutions.) On the other hand, no spoilers allowed. Discuss your favorite three-letter word.
[If any enterprising reader wants to make an interactive version of this puzzle, please put the link below.]
So what do these puzzles have to do with one of the most important achievements in computer science? Bear with me.
Fifty years ago, computer scientists discovered that many naturally occurring problems, such as the best way to stack suitcases of different sizes in the trunk of a car, became so complex when scaled up that computers could solve them within a reasonable amount of time. I discovered that it becomes impossible to solve the problem. Also, surprisingly, we found it equally difficult to get approximate answers to these suitcase and boot questions.
An analogy to today’s puzzles is that a puzzle has a correct solution, but it also has an “approximate” solution. As we have seen, you can get a full score or a partial score. Imagine scaling up this type of puzzle with more clues, letters, and arrows. Distinguishing between puzzles that give a complete solution and puzzles that give a partial solution is so complex that computers cannot do it in a reasonable amount of time.
This field, or the study of the “difficulty of approximation,” is closely related to a surprising result in mathematical proofs: the PCP theorem. Usually when you want to check a mathematical proof, you have to check it line by line to make sure there are no errors. Like when a teacher scrutinizes your work to make sure all your reasoning is a logical step.
However, the PCP theorem shows that there is no need to check the proof line by line to make sure there are no mistakes. Instead, you can rewrite the proof so that you can check it by randomly selecting just two or three bits from the proof and checking only those bits. That is, it checks whether the bit is 0 or 0 at two or three points. a 1. Just a few bits! For all mathematical proofs!
The above puzzle is a simplified version of the PCP theorem, says Dana Moszkovitz. She came up with it as a way to introduce the subject to her students. She further added: “Virtually all the known results we have today regarding the hardness of approximations begin with her PCP theorem in the form of a word puzzle.”
Yes, this is a bit confusing since the word puzzle itself does not check the proof. However, if you consider that each word is essentially a “check” for the complete solution, the link will appear.
The PCP theorem (the letters represent probabilistically testable proofs) was a major theoretical advance that promised important practical applications. For example, a computer with less memory will be able to check whether a larger computer has done something correctly very efficiently, such as an iPhone checking the integrity of a program in the cloud. This technology is already used in blockchain. Israeli high-tech unicorn StarkWare.
If you would like to learn more about the PCP theorem, This is a great piece of work by Danna It was published in the Association for Computing Machinery’s student magazine, XRDS.
I am currently a resident science communicator at the Simons Institute for Computing Theory at the University of California, Berkeley.
Since 2015, I have been posting puzzles here every other Monday. Always looking for great puzzles. If you would like to suggest anything, please email me.
