| I'm a big fan of the mind-bending questions at the heart of theoretical computer science. But I'll be the first to admit that the field has a branding problem. Consider, for instance, its most famous open question, about the essence of mathematical difficulty and the very nature of what's knowable. Does this profound question have an appropriately evocative name? Well, it's called the P versus NP problem. You be the judge.
Bland names like P versus NP are common in the subfield of computational complexity theory, in which researchers classify problems according to the resources required to solve them. P and NP are the names of two of the most famous complexity classes: They stand for "polynomial time" and "nondeterministic polynomial time," respectively. If you think that's a mouthful, just wait until you get to BPP (bounded-error probabilistic polynomial time) and MIP (multi-prover interactive proof). A complexity theorist once lamented to me that the deepest mysteries in the field sound like airport codes. (Indeed, a MIP could tell you the best route from MIA to MSP, though plain old P would also suffice.)
Yet hidden among all those mind-numbing acronyms are a few true gems. Take the family of circuit classes, which includes classes called AC (alternating circuit) and TC (threshold circuit). You might guess that the closely related complexity class NC is named for another kind of circuit. Actually, it stands for "Nick's class," a nod to the computer scientist Nick Pippenger. There's also SC (Steve's class), named for the complexity theorist Steve Cook. The class MA, meanwhile, stands for "Merlin-Arthur," after a fanciful scenario in which the legendary king interrogates a powerful wizard.
These sorts of names don't just turn up in complexity classes. Delightful terms like "Gaussian pancake" and "quantum snake walk" have cropped up unexpectedly throughout my reporting. There's actually a lot of whimsy in computer science if you know where to look.
What's New and Noteworthy
When it comes to names that evoke a sense of mystery, it's hard to do better than "oracle." Theoretical computer scientists use this term to refer to fantastical entities that can answer specific questions instantly without revealing anything about how they got the answer. When complexity theorists have difficulty proving theorems about the relationship between two complexity classes, they sometimes investigate how those classes would be related in an imaginary world in which every computer can consult a specific type of oracle. Strange as they may seem, these thought experiments can illuminate fundamental questions about computation in the real world.
Playful names feel especially appropriate for seemingly simple concepts that turn out to be surprisingly deep. One great example is the pigeonhole principle, which states that if you stuff some number of pigeons into a smaller number of pigeonholes, at least one hole will contain more than one pigeon. This sounds like basic common sense, but it turns out to have many unexpected applications to complexity theory. There's also the busy beaver game — a math problem about the craziest things that simple computer programs can do. It gets fiendishly complicated even for programs whose code fits on an index card.
Fun names are good for more than just amusing outside observers like me. They can also help focus the efforts of researchers in fields where it's easy to get lost in all the jargon. This was a theme of a conversation I had last year with the complexity theorist Russell Impagliazzo. In 1995, Impagliazzo wrote a famous paper that reframed the P versus NP problem and several related problems as a question about five hypothetical worlds with whimsical names — my favorites are Pessiland and Cryptomania. "It was a way to show how these ideas would actually influence the world without getting caught up in quantitative details," Impagliazzo told me. His five worlds captured the imagination of a new generation of complexity theorists and continue to guide research to this day.
Impagliazzo is not the only computer scientist who's thought a lot about what makes a good name. Way back in 1974, the pioneering computer scientist Donald Knuth put out a request for a collective name for a group of problems that are now (alas) known as NP-hard problems. There were many more interesting proposals, but no consensus — as Knuth observed, "Creative research workers are as full of ideas for new terminology as they are empty of enthusiasm for adopting it." In 2020, Susan D'Agostino spoke to Knuth about his life's work and why language matters in computer science. As Knuth put it, "The best way to communicate from one human being to another is through story." A good name can go a long way. | 
