Today’s puzzle illuminates one of the smash hits of theoretical computer science, a mind-boggling result that left even experts in the field gobsmacked.
We’ll get to that result (the PCP theorem) later. But first, to the challenge!
It’s a word puzzle. Crossword-style clues each point to a vertical column. The answer to each clue is a three-letter word, made up from the three letters that the clue points to.
Let’s solve this one together. An animal that’s three letters? How about “bat”?
Each 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 carry on. Here’s one way to complete the grid.
Note that this grid is not a full solution. The three top clues are fully answered. I’ve highlighted the green arrows from the clue ‘verb’, which points to ‘pay’. But the three bottom clues are only partially solved. Food 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 full 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 is OK to get a partial solution.” In fact, that is what makes it fun. The aim is to get the highest possible score.
Here are three examples, in increasing order of difficulty.
Problem 1
Problem 2
Problem 3
I’ll be back at 5pm UK with full solutions. (There are possibly many full solutions.) Meanwhile, NO SPOILERS. Please discuss your favourite three letter words.
[If any enterprising reader wants to make an interactive version of this puzzle, please put the link below.]
So, what have these puzzles got to do with one of the most important results in computer science? Bear with.
Fifty years ago, computer scientists discovered that many naturally occurring problems, such as how best to stack different sizes of suitcase in a car boot, become so complex once you scale them up that computers are unable to solve them in a reasonable time. It also turns out, surprisingly, that getting approximate answers to these suitcase-in-a-boot problems is just as hard.
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 you were to scale up this type of puzzle with more clues, letters, and arrows. Distinguishing puzzles that give a perfect solution, and ones that give a partial solution is so complex that computers cannot do it in any reasonable time.
This field – the study of “hardness of approximation” – has deep connections to the PCP theorem, a stunning result that concerns mathematical proofs. Usually when you want to check a mathematical proof you need to check it line by line to see if there are no mistakes. Like when a teacher goes through your workings to make sure every piece of deduction is a logical step.
The PCP theorem, however, shows that you do not need to check a proof line by line in order 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 only two or three bits from the proof and checking only these bits, that is, checking at two or three points whether the bit is either a 0 or a 1. Just a couple of 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 of introducing the subject to her students. She adds: “Practically *all* known results we have today about hardness of approximation start with the PCP theorem in the word puzzle form.”
Yes, this is a bit confusing, since the word puzzle is not itself about checking proofs. However, you can see the link if you consider each word as essentially a “check” of a full solution.
The PCP theorem (the letters stand for probabilistically checkable proof) was a huge theoretical advance, and one that promises important practical applications. For example, it permits a computer with a small memory to check very efficiently that a large computer has done something correctly, such as, say, an iphone checking the integrity of a program in the cloud. This technology is already being used in blockchains, such as 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 science communicator in residence at the Simons Institute for the Theory of Computing, University of California, Berkeley.
I’ve been setting a puzzle here on alternate Mondays since 2015. I’m always on the look-out for great puzzles. If you would like to suggest one, email me.
