Ask a Magic 8 ball a question, and it will answer yes, no, or something annoyingly indecisive. We think of it as a children’s toy, but theoretical computer scientists use a similar tool. They often imagine that 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 computing landscape.
Researchers who invoke oracles work in a subfield of computer science called computational complexity theory. They worry about the difficulty inherent in 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 much more difficult but have easy to verify solutions, while still others are easy to solve. quantum computers but apparently difficult for ordinary people.
Complexity theorists want to understand whether these apparent differences in difficulty are fundamental. Is there something inherently difficult about some problems, or are we just not smart enough to come up with a good solution? Researchers approach these questions by categorizing problems into “complexity course» – all the easy problems go to one class, for example, and all the easy problems to check go to another – and prove theorems about the relationships between these classes.
Unfortunately, mapping the landscape of IT challenges has proven to be a difficult task. So in the mid-1970s, some researchers began to study what would happen if the calculation rules were different. This is where oracles come into play.
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 are always right – a benefit of being fictional. Additionally, a 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 short, they can reveal hidden links between different complexity classes.
Take the two most famous complexity courses. There is the class of easy-to-solve problems, which researchers call “P”, and the class of easy-to-verify problems, which researchers call “NP”. Are all problems that are easy to check also easy to fix? 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 is not equal to P, but they cannot prove it, even though they have long tried to pin down the relationship between the two classes. over 50 years old.
The Oracles helped them better understand what they were working with. Researchers have invented oracles that answer questions to solve many different problems. In a world where every computer had a hotline to one of these oracles, all problems that were easy to verify would also be easy to solve, and P would equal NP. But other oracles, less useful, have the opposite effect. In a world populated by these oracles, P and NP would clearly be different.
Researchers have used this knowledge to better understand the P versus NP problem. Early attempts to determine the relationship between P and NP used an elegant trick called diagonalization this had been essential for other major results in computer science. But researchers soon accomplished that any proof based on diagonalization would equally apply to any world where every computer can consult the same oracle. This sounded the death knell, as the oracles changed the answer to the question P versus NP. 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 are clearly equivalent. This means that any diagonalization-based solution to the P versus NP problem would be contradictory. The researchers concluded that they would need new techniques to make progress.
Oracles have also been useful in the study of quantum computing. In the 1980s and 1990s, researchers discovered ways to harness quantum physics to quickly solve some problems that seemed difficult for ordinary “classical” computers to solve. But did these problems just seem difficult, or were they really difficult? Proving it one way or another would require radically new mathematical techniques.
For this reason, researchers have studied how quantum computers behave on problems involving oracles. These efforts can provide indirect proof that quantum computers are actually more powerful than classical computers and can help researchers explore qualitatively new tasks where quantum computers could excel. Sometimes they can even have practical applications. In 1994, applied mathematician Peter Shor was inspired by a recent oracle result develop a fast quantum algorithm to factor large numbers — a task whose apparent difficulty underpins the cryptographic systems that keep our data secure online. Shor’s discovery launched a race to build powerful quantum computers that continues today.
It’s difficult to predict the future of complexity theory, but it’s not as difficult to answer all the questions about the field’s trajectory. Will researchers continue to consult oracles? The signs point to yes.