The Researcher Who Explores Computation by Conjuring New Worlds | Quanta Magazine

Imagine you’re on a quest to understand the very nature of computation. You’re deep in the wilderness, far from any paths, and inscrutable messages are carved into the trunks of trees all around you — BPP, AC⁰[m], Σ₂P, YACC, and hundreds of others. The glyphs are trying to tell you something, but where to begin? You can’t even keep them all straight.

Few researchers have done as much as Russell Impagliazzo to cut through this seeming chaos. For 40 years, Impagliazzo has worked at the forefront of computational complexity theory, the study of the intrinsic difficulty of different problems. The most famous open question in this field, called the P versus NP problem, asks whether many seemingly hard computational problems are actually easy — with the right algorithm. An answer would have far-reaching implications for science and the security of modern cryptography.

In the 1980s and 1990s, Impagliazzo played a leading role in unifying the theoretical foundations of cryptography. In 1995, he articulated the significance of these new developments in an iconic paper that reformulated possible solutions to P versus NP and a handful of related problems in the language of five hypothetical worlds we might inhabit, whimsically dubbed Algorithmica, Heuristica, Pessiland, Minicrypt and Cryptomania. Impagliazzo’s five worlds have inspired a generation of researchers, and they continue to guide research in the flourishing subfield of meta-complexity.

And these aren’t the only worlds he’s dreamed up. Impagliazzo has been a lifelong aficionado of tabletop role-playing games like Dungeons and Dragons, and he delights in inventing new sets of rules and new settings to explore. The same playful spirit animates his 30-year practice of improvisational comedy.

Impagliazzo also did foundational work elucidating the fundamental role of randomness in computation. In the late 1970s, computer scientists discovered that randomness could sometimes improve algorithms for solving inherently deterministic problems — a counterintuitive finding that perplexed researchers for years. Impagliazzo’s work with the complexity theorist Avi Wigderson and other researchers in the 1990s showed that if certain computational problems really are fundamentally hard, then it’s always possible to convert algorithms that use randomness into deterministic ones. And conversely, proving that randomness can be eliminated from any algorithm would also prove that truly hard problems exist.

Quanta spoke with Impagliazzo about the difference between hard problems and hard puzzles, consulting oracles, and the mathematical lessons of improv comedy. The interview has been condensed and edited for clarity.

When did you first get interested in mathematics?

I was interested in math even before I really knew what it was. In third grade, my math grades started slipping because we were supposed to memorize our multiplication tables, and I refused. My mother said, “But Russell, you love math, why aren’t you doing this?” And I said, “That’s not math, that’s memorization. Real math doesn’t involve memorization.” All I’d learned at that point was arithmetic, so I’m not sure where I got the notion that math was about abstract concepts.

What about computer science? Parts of the field are very abstract, but they aren’t what most people first encounter.

In high school, I’d had a programming course in BASIC, but it was really hard to get anything done. The programs had to be transferred to paper tapes, which had to be run through this very old computer that often malfunctioned and ripped your paper in half. So I thought computer science was dreadfully dull.

I intended to study logic. But a lot of the concepts, when you tried to actually formalize them, involved computation and especially limits on computation. Questions like “How do we know things in mathematics are true?” and “How do we understand the difficulty of doing mathematics?” led to theoretical computer science, and complexity theory especially.

Some of your most famous work explores the connections between cryptography and computational complexity theory. Why are those two fields related?

When you’re setting up a cryptographic system, you need to distinguish between legitimate users — the people you want to grant access to — and everybody else. Computationally difficult problems give us a way to distinguish these groups based on what they know. But if you want knowing the answer to a problem to be a way of distinguishing two groups of people, you can’t just use any hard problem — you need a hard puzzle.

What’s the difference between a problem and a puzzle?

In general, the person posing a problem might not know the answer. A puzzle is a problem designed with an answer in mind. So why do we need a puzzle? Because we need to be able to determine whether a person who supposedly solved it actually did. In everyday life, we use puzzles for amusement, but we also use them in classrooms to test whether people understood the material. This is what happens in cryptography: We’re using puzzles to test someone’s knowledge.

The difference between the five worlds is how they answer the questions “Are there hard problems?” and “Are there hard puzzles?”

How do those different answers play out?

In the first world, Algorithmica, no problems are hard. You don’t have to know how someone designed your problem: You can always solve it. Heuristica is saying, “Well, maybe a few problems are hard.” Then we get to Pessiland, where many problems are hard, but most puzzles aren’t. Almost any problem that I make up where I know the solution, you’re going to be able to solve it too. All of these worlds are bad for cryptography.

In Minicrypt, I can create puzzles that I know how to solve that are still really challenging for you. And finally, Cryptomania is a world in which two people can stand in a public location where an eavesdropper can hear and together create a puzzle that’s still hard for the eavesdropper.

What motivated you to write the five worlds paper?

At the time, it was known that different answers to the P versus NP question would have a big impact on what kind of problems we can solve and also what kind of security we can hope for, but the qualitative distinctions between different forms of easiness and hardness were not really clear.

There was a very insightful paper just a few years earlier that laid out the distinctions using many interrelated questions with like 20 possible answers. One reason why I wanted to write the five worlds paper was we had made a huge amount of progress in those few years. It would have been hard to find names for 20 possible worlds.

So why frame it that way, as different worlds with quirky names?

I had agreed to write this paper for a conference. I was staying up late at night trying to figure out what I was going to say, and somewhere around 1 a.m. the different worlds framing seemed like a good idea. And then I read it the next morning and it still seemed like an OK idea — it was a way to show how these ideas would actually influence the world without getting caught up in quantitative details. What makes me happiest about this paper is that I hear from people doing research in complexity that this was the paper that got them interested in the field as undergraduates.

Have researchers ruled out any of the five possible worlds?

We’re actually adding more — people have started talking about Obfustopia as a world of even stronger cryptographic tools. It is a little depressing that we made so much progress in the late 1980s and haven’t eliminated any worlds since then. But on the other hand, we know a lot more about the connections between worlds and have a much clearer picture of what each world would look like.

Hypothetical worlds also play another role in complexity theory, in proofs that assume the existence of “oracles.” So, first of all, what exactly is an oracle?

Imagine someone builds an ingenious device that can solve some problem without us knowing an algorithm for solving that problem. That’s what an oracle is. If we had such a miraculous device and we put it inside our computers, it could shift where the line is between what is computable and what is not computable.

Do researchers think these magic boxes could actually exist?

No, they probably do not exist. Early on, oracle results were somewhat controversial because they’re so hypothetical. But one way they can be very enlightening is when the oracle is used to model an ideal situation. Say you’re trying to show that A doesn’t necessarily imply B. You start with the setting where you have the most extreme A and show that that’s still not enough to guarantee B. If you can show that even if all the odds are in your favor you still can’t prove something, that’s really strong evidence that it’s going to be difficult to prove.

You’ve also discovered links between computational hardness and randomness. How does that connection work?

It’s really a way of saying that if you don’t understand something, then it might seem random. Suppose I say I’m thinking of a number between one and a thousand. If I pick the number at random, you have a one-in-a-thousand chance of guessing it. And if I ask — following Monty Python — “In miles per hour, what’s the average airspeed of a European swallow?” you’ve got about the same chance. It probably goes more than one mile an hour, and it probably doesn’t go more than a thousand miles per hour.

This is not actually random — it’s a deterministically answerable question. We could just measure all the swallows flying around, but it’s kind of hard to determine with limited resources, like not having a budget for measuring swallow speeds and not having an infinite supply of swallows.

So the insight is that hard problems whose solutions we don’t know can provide a source of “pseudorandom” numbers that look random.

Speaking of Monty Python, I know you’ve been doing improv comedy for a long time now — how did you get started?

I started as an assistant professor in San Diego in 1991. And around ’94 or so, I thought, “I really don’t have much of a life outside of the department.” So I got the free weekly paper, and I looked through the list of clubs and activities. I eliminated everything except improv comedy — I thought it was at least plausible that I’d be OK at it. I met my wife in that beginner class.

What did she think?

She says I was really awful. When you’re a logician, you’re trained to always think about the nuance of every word. You don’t want to say something incorrect. Improv is great in that it reverses that: The point is not to say something perfect but to make up something quickly. It was the opposite of the rest of my life.

My now-wife took a break from the class, and when she returned a year later, I managed to impress her. That was 30 years ago. I still take the same class with the same instructor.

Has doing improv changed the way you approach your research?

It’s good practice for not being hypercritical about every thought you have. That’s especially helpful in collaborations. When doing work with other people, I used to say things like, “But that idea won’t work for the following reason. That’s not literally true.” In improv, you’re always supposed to accept what your partner says. And I think that’s a good attitude to have, especially when you’re doing research with students: Don’t dismiss something they say just because you know it’s incorrect. There are lots of good ideas that aren’t 100% correct.

Like what?

When you’re trying to get intuition for a problem, one thing that helps is to start with some simplifying assumptions. Those assumptions are usually not true, but they can help you come up with a road map. Say, “If I had an elephant, I could get over the mountains. Of course, I don’t have an elephant. But if I did, here’s how I would do it.” And then you realize, “Well, maybe I don’t need an elephant for this step. A mule would be fine.”

What about your love of role-playing games — has that influenced your work at all?

It may not have influenced all my research, but it certainly did influence my five worlds paper. I’ve always had a general interest in fantasy and science fiction and coming up with different possible worlds — what would things be like if everything was different?

Why are role-playing games such a compelling way to explore hypothetical worlds?

People who are into speculative fiction have always invented worlds. Tolkien is most famous for it, and he had such a massive imagination that his world actually felt lived in. For those of us who aren’t as imaginative, the best way to achieve that is to invite people into your setting, and a game is a way of doing that. Now it’s not just my world. It may have started how I imagined it, but just like in any collaboration, because of everyone else’s contributions it’s evolved way past that.