Why Computer Scientists Consult Oracles

Pose a question to a Magic 8 Ball, and it’ll answer yes, no or something annoyingly indecisive. We think of it as a kid’s toy, but theoretical computer scientists employ a similar tool. They often imagine they can consult hypothetical devices called oracles that can instantly, and correctly, answer specific questions. These fanciful thought experiments have inspired new algorithms and helped researchers map the landscape of computation.

The researchers who invoke oracles work in a subfield of computer science called computational complexity theory. They’re concerned with the inherent difficulty of problems such as determining whether a number is prime or finding the shortest path between two points in a network. Some problems are easy to solve, others seem much harder but have solutions that are easy to check, while still others are easy for quantum computers but seemingly hard for ordinary ones.

Complexity theorists want to understand whether these apparent differences in difficulty are fundamental. Is there something intrinsically hard about certain problems, or are we just not clever enough to come up with a good solution? Researchers address such questions by sorting problems into “complexity classes” — all the easy problems go in one class, for example, and all the easy-to-check problems go in another — and proving theorems about the relationships between those classes.

Unfortunately, mapping the landscape of computational difficulty has turned out to be, well, difficult. So in the mid-1970s, some researchers began to study what would happen if the rules of computation were different. That’s where oracles come in.

Like Magic 8 Balls, oracles are devices that immediately answer yes-or-no questions without revealing anything about their inner workings. Unlike Magic 8 Balls, they always say either yes or no, and they’re always correct — an advantage of being fictional. In addition, any given oracle will only answer a specific type of question, such as “Is this number prime?”

What makes these fictional devices useful for understanding the real world? In brief, they can reveal hidden connections between different complexity classes.

Take the two most famous complexity classes. There’s the class of problems that are easy to solve, which researchers call “P,” and the class of problems that are easy to check, which researchers call “NP.” Are all easy-to-check problems also easy to solve? If so, that would mean that NP would equal P, and all encryption would be easy to crack (among other consequences). Complexity theorists suspect that NP does not equal P, but they can’t prove it, even though they’ve been trying to pin down the relationship between the two classes for over 50 years.

Oracles have helped them better understand what they’re working with. Researchers have invented oracles that answer questions that help solve many different problems. In a world where every computer had a hotline to one of these oracles, all easy-to-check problems would also be easy to solve, and P would equal NP. But other, less helpful oracles have the opposite effect. In a world populated by these oracles, P and NP would be provably different.

Researchers have used this knowledge to get a better grasp on the P versus NP problem. The first attempts at determining the relationship between P and NP used an elegant trick called diagonalization that had been essential for other major results in computer science. But researchers soon realized that any proof based on diagonalization would also apply to any world where every computer can consult the same oracle. This spelled doom, as oracles change the answer to the P versus NP question. If researchers could use diagonalization to prove that P and NP are different in the real world, the same proof would imply that P and NP are different in an oracle-infused world where they’re clearly equivalent. That means any diagonalization-based solution to the P versus NP problem would be self-contradictory. Researchers concluded that they’d need new techniques to make progress.

Oracles have also been helpful in the study of quantum computing. In the 1980s and 1990s, researchers discovered ways to harness quantum physics to rapidly solve certain problems that seemed hard for ordinary “classical” computers. But did these problems just seem hard, or were they truly hard? Proving it one way or another would require radically new mathematical techniques.

Because of this, researchers have studied how quantum computers fare on problems involving oracles. These efforts can provide indirect evidence that quantum computers really are more powerful than classical ones, and they can help researchers explore qualitatively new tasks where quantum computers might excel. Sometimes, they can even have practical applications. In 1994, the applied mathematician Peter Shor was inspired by a recent oracle result to develop a fast quantum algorithm for factoring large numbers — a task whose apparent difficulty underlies the cryptographic systems that keep our online data secure. Shor’s discovery kicked off a race to build powerful quantum computers that continues to this day.

It’s hard to predict the future of complexity theory, but not every question about the trajectory of the field is equally hard to answer. Will researchers continue to consult oracles? Signs point to yes.