by Today’s puzzle represents one of the highlights of theoretical computer science, a fascinating result that has left even experts in the field gobsmacked.
We will derive that result (the PCP theorem) later. But first, with the challenge!
It’s a word puzzle. Crossword style clues each point on a vertical column. The answer to each clue is a three-letter word, made up of the three letters the clue points to.
Let’s solve this one together. Animal that three letter? How about a “bat”?
Every time we can enter a convincing answer we get a point for each letter. “Bat” gives us a score of 3.
Now, let’s move on. This is one way to complete the grid.
Note that this grid is not a complete solution. The top three prompts are fully answered. I’ve highlighted the green arrows from the ‘verb’ clue, which means ‘pay’. But the bottom three clues are only partially solved. Food is ‘pey’, not ‘pea’. However, we can award ourselves a point for any letters in a potentially correct answer, so ‘pey’ gets us 2 points, for the two correct letters in ‘pea’. Total score: 15 points.
Here’s how you’d get a full solution, with a maximum score of 18. Of course, “cat” was a much more obvious place to start!
The point of this answer, says Dana Moshkovitz, a professor of computer science at the University of Texas at Austin, is that “it’s OK to have a partial solution.” In fact, that’s what makes it fun. The aim is to get the highest possible score.
Here are three examples, in order of increasing difficulty.
Problem 1
Problem 2
Problem 3
I’ll be back at 5pm UK with full solutions. (There may be many complete solutions.) Meanwhile, NO SPOILERS. Please discuss your favorite three letter words.
[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 findings in computer science? Bear with.
Fifty years ago, computer scientists discovered that many naturally occurring problems, such as how best to stack bags of different sizes in a car boot, become so complex when you scale them up that computers can’t solve them. resolved in a reasonable time. It also turns out, not surprisingly, that it is so difficult to find answers to the following case-in-shoe problems.
The analogy with today’s puzzle is that the puzzle has a correct solution, but also has “approximate” solutions. As we have seen, you can get a full score, and you can also get partial scores. Imagine that you were to increase this type of puzzle with more clues, letters and arrows. It’s so complex between the puzzles that give a perfect solution, and the ones that give a partial solution that computers can’t do it in any reasonable time.
This field has deep connections – the study of the “hardness of approximation” with the PCP theorem, a remarkable result of mathematical proofs. Usually when you want to check a mathematical proof you need to check it line by line to see if there are any mistakes. Like when a teacher goes through your work to make sure each piece of deduction is a logical step.
However, the PCP theorem shows that you do not need to check a proof step by step to make sure there are no mistakes. Instead, you can rewrite the proof in such a way that you can check it by randomly choosing two or three bits from the proof and checking only these bits, that is, checking at two or three points is the bit a 0 or a 1. Only a few bits! For any mathematical proof!
The answer above is a simplified version of the PCP theorem, says Dana Moshkovitz, who came up with it as a way to introduce the subject to her students. She says: “Almost *every* known result we have today about the hardness of the approximation to the PCP theorem comes in word-answer form.”
Yes, this is a bit confusing, since the word puzzle itself is not about checking proofs. However, you can see the link if you consider it basically a “check” on the overall resolution of each word.
The PCP theorem (the letters stand for some sort of checkable proof) was a huge theoretical advance, and one that promises important practical applications. For example, it allows a computer with a small memory to very efficiently check that a large computer has done something right, like, say, an iPhone checking the integrity of a program in the cloud. This technology is already being used in blockchains, for example by Israeli tech unicorn StarkWare.
If you want to learn more about the PCP theorem, here’s a great piece by Dana that was in XRDS, the student magazine of the Association for Computing Machinery.
I am currently a science communicator in residence at the Simons Institute for the Theory of Computation, University of California, Berkeley.
I’ve been setting a puzzle here every other Monday since 2015. I’m always on the lookout for great puzzles. If you would like to recommend one, please email me.
