Why Computer Scientists Consult Oracle

Put a question to a Magic 8 Ball, and it will answer yes, no or something annoyingly indeterminate. We think of it as a child’s toy, but theoretical computer scientists use similar tools. They often imagine that they can consult hypothetical devices called oracles that can quickly, and correctly, answer specific questions. These imaginative thought experiments have inspired new algorithms and helped researchers map the computational landscape.

Researchers who invoke oracles work in a subfield of computer science called computational complexity theory. They are concerned with the inherent difficulty of problems such as determining whether a number is prime or finding the shortest path between two points on a network. Some problems are easy to solve, others seem more difficult but have solutions that are easy to check, while others are easy for quantum computers but it seems difficult for ordinary people.

Complexity theorists want to understand whether these apparent differences in difficulty matter. Is there something too difficult about certain problems, or are we not smart enough to come up with a good solution? Researchers answer those questions by sorting the problems into “complex classes” — all easy problems go into one class, for example, and all easy-to-check problems go into another — and prove theorems about relationships between classes.

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

Like the 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 yes or no, and they’re always right – an advantage of being fictional. Additionally, any given oracle will only answer a certain type of question, such as “Is this number prime?”

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

Take the two most popular types of complexity. There are the type of problems that are easy to solve, which researchers call “P,” and the type of problems that are easy to analyze, which researchers call “NP.” Are all easily diagnosed problems also easily solved? If so, that means NP is equal to P, and all encryption easy to break (among other consequences). Complexity theorists suspect that NP is not equivalent to P, but they cannot prove it, although they try to point out the relationship between the two classes for more than 50 years.

Oracles help them better understand what they are working on. Researchers have invented oracles that answer questions that help solve many different problems. In a world where every computer has a hotline to one of these oracles, all easy-to-analyze problems are also easy to solve, and P equals NP. But other, less helpful oracles have the opposite effect. In a world inhabited by these oracles, P and NP would be very different.

Researchers use this knowledge to better understand the P versus NP problem. The first attempt to determine the relationship between P and NP used an elegant trick called diagonalization which is important for other major results in computer science. But the researchers soon realizing that any proof based on diagonalization also applies to any world where every computer can consult the same oracle. This spelled doom, as the oracles changed the answer to the P versus NP question. If researchers can use diagonalization to prove that P and NP are distinct in the real world, the same proof would imply that P and NP are distinct in an oracle-infused world where they are clearly equivalent. That means any diagonalization-based solution to the P versus NP problem would be self-contradictory. The researchers concluded that they needed new methods to progress.

Oracles have also helped in the study of quantum computing. In the 1980s and 1990s, researchers discovered ways to use quantum physics to quickly solve some problems that seemed difficult for ordinary “classical” computers. But do these problems seem difficult, or are they really difficult? Proving it one way or another requires new mathematical methods.

For this reason, researchers have studied how quantum computers work on problems involving oracles. These efforts are paying off indirect evidence that quantum computers are more powerful than classical ones, and this will help researchers to explore qualitatively new tasks where quantum computers can succeed. Sometimes, they may even have practical applications. In 1994, applied mathematician Peter Shor was inspired by a recent oracle results to develop a fast quantum algorithm for factoring large numbers — a task whose apparent difficulty underlies the cryptographic systems that keep our online data safe. Shor’s discovery started a race to build powerful quantum computers that continues to this day.

Predicting the future of complexity theory is difficult, but not all questions about the field’s trajectory are equally difficult to answer. Will researchers continue to consult oracles? The signs point to yes.