Today’s puzzle highlights one of the great hits of theoretical computer science, a startling result that even experts in the field struck.
We will arrive at that result (the PCP statement) later. But first after the challenge!
This is a word puzzle. Crossword-style clues each point to a vertical column. The answer to each clue is a three-letter word, made up of the three letters to which the clue refers.
Let’s solve this one together. An animal that is three letters? What about “bat”?
Every time we can put in a convincing answer, we get a point for each letter. “Bat” gives us a score of 3.
Now let’s move on. Here is one way to complete the grid.
Note that this grid is not a complete solution. The three top clues are fully answered. I highlighted the green arrows from the clue ‘verb’, pointing to ‘pay’. But the bottom three clues are only partially solved. Kos points to ‘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 could get a complete solution, with a maximum score of 18. Of course, “cat” was a much more obvious place to start!
The point of this puzzle, says Dana Moshkovitz, 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 goal is to get the highest possible score.
Here are three examples, in increasing difficulty.
Problem 1
Problem 2
Problem 3
I’ll be back at 5pm UK with full solutions. (There are potentially many complete solutions.) In the meantime, 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 mysteries have to do with one of the most important results in computer science? Bear.
Fifty years ago, computer scientists discovered that many naturally occurring problems, such as how best to stack different-sized suitcases in a car trunk, become so complex once you scale them up that computers can’t solve them in a reasonable amount of time. It also turns out, surprisingly, that it is just as difficult to get approximate answers to these suitcase-in-a-boot problems.
The analogy with today’s puzzle is that the puzzle has a correct solution, but it also has “approximate” solutions. As we have seen, you can get full score, and you can also get partial scores. Imagine if you were to enlarge this type of puzzle with more clues, letters and arrows. Distinguishing between puzzles that give a perfect solution and ones that give a partial solution is so complex that computers cannot do it in any reasonable amount of time.
This field – the study of “hardness of approximation” – has deep connections with the PCP theorem, a stunning result in terms of mathematical proofs. Usually when you want to check a mathematical proof, you have 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 inference is a logical step.
However, the PCP statement shows that you don’t need to check a test line by line to make sure there are no errors. Instead, you can rewrite the proof in such a way that you can check it by just picking two or three bits at random from the proof and checking just these bits, that is, checking at two or three points whether the bit either a 0 or a 1. Just a few bits! For any mathematical proof!
The puzzle 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 adds: “Virtually *all* known results we have today about the hardness of approximation start with the PCP theorem in word puzzle form.”
Yes, it’s a bit confusing, since the word puzzle is not itself about checking evidence. However, you can see the link if you view each word as essentially a “check” of a complete solution.
The PCP theorem (the letters stand for probabilistically verifiable proof) was a major 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 correctly, such as an iPhone checking the integrity of a program in the cloud. This technology is already used in blockchains, such as by Israeli tech unicorn StarkWare.
If you want to learn more about the PCP statement, here is a great piece by Dana it was in XRDS, the student magazine of the Society for Computing Machinery.
I am currently science communicator in residence at the Simons Institute for the Theory of Computing, University of California, Berkeley.
I’ve been doing a puzzle here on alternate Mondays since 2015. I’m always on the lookout for great puzzles. If you want to suggest one, email me.
