Today’s puzzle sheds light on one of the greatest achievements of theoretical computer science; This is a mind-blowing result that has stunned even experts in the field.
We will reach this result (PCP theorem) later. But first, take on the challenge!
This is a word puzzle. The puzzle-style clues each point to 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 together. A three-letter animal? How about “Bat”?
Every time we can give a convincing answer, we get one point for each letter. “Bat” gives us 3 points.
Now let’s continue. Here’s one way to complete the grid.
Note that this guide is not a complete solution. The top three tips are fully answered. I highlighted the green arrows on the clue ‘verb’ meaning ‘pay’. But the bottom three clues were only partially solved. The food points to ‘pey’, not ‘pea’. But we can potentially give ourselves one point for any letter in a correct answer, so for two correct letters in ‘pea’ ‘pey’ gives us 2 points. Total score: 15 points.
Here’s how you can achieve a complete solution with a maximum of 18 points. Of course “cat” was a much more obvious place to start!
The point of this puzzle is that “it’s okay to find a partial solution,” says Dana Moshkovitz, a professor of computer science at the University of Texas at Austin. Actually, that’s what makes the job fun. The aim is to get the highest score possible.
Here are three examples in increasing order of difficulty.
Problem 1
Problem 2
Problem 3
I will return to the UK at 5pm with full solutions. (There are probably many complete solutions.) By the way, NO SPOILERS. Please 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 results in computer science? Be patient.
Fifty years ago, computer scientists discovered that many naturally occurring problems, such as how best to stack suitcases of different sizes in a car trunk, became too complex when scaled up for computers to solve them in a reasonable amount of time. And, surprisingly, getting approximate answers to these baggage problems turned out to be just as difficult.
The similarity to today’s puzzle is that the puzzle has a correct solution, but there are also “approximate” solutions. As we see, you can get full points or partial points. Imagine enlarging this type of puzzle with more clues, letters and arrows. Distinguishing between puzzles that provide a perfect solution and those that provide a partial solution is so complex that computers cannot do it in a reasonable amount of time.
This field, the study of “hardness of approximation”, has deep connections with the PCP theorem, a striking result concerning 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 errors. Just like a teacher reviewing your work to make sure each inference is a logical step.
But the PCP theorem shows that you don’t need to check the proof line by line to make sure there are no errors. Instead, you can rewrite the proof so that you can randomly pick only two or three bits from the proof and check only those bits, i.e., checking whether the bit is 0 or 0 at two or three points. a 1. Just a few pieces! For any mathematical proof!
The puzzle above is a simplified version of the PCP theorem, says Dana Moshkovitz, who came up with this puzzle as a way to introduce the subject to her students. She adds: “Practically all the known results we have today about the hardness of approximation begin with the PCP theorem in word puzzle form.”
Yes, this is a bit confusing because the word puzzle itself is not about checking the evidence. But if you treat each word as essentially a “check-in” of a complete solution, you can see the connection.
The PCP theorem (the letters stand for probabilistically checkable proof) was a huge theoretical advance and promised important practical applications. For example, it allows a computer with small memory to check whether a large computer is doing something right very efficiently, much like an iPhone checks the integrity of a program in the cloud. This technology is already used in blockchains such as Israeli tech unicorn StarkWare.
If you want to learn more about the PCP theorem, here Dana has a great article in the Computing Machinery Association’s student magazine, XRDS.
I am currently the science communicator in residence at the Simons Institute for Computer Theory at the University of California, Berkeley.
I have been preparing puzzles here alternately on Mondays since 2015. I’m always on the lookout for great puzzles. If you’d like to recommend one, email me.