The original version of This story appeared in Quanta Magazine.
Ask a question to a magical 8 -ball, and it will answer yes, no, or something annoyingly indecisive. We consider it a children’s toys, but theoretical computer scientists use a similar tool. They often think they can consult hypothetical devices called oracles, which can answer specific questions immediately and correctly. These fantasy thought experiments have inspired new algorithms and have helped researchers to map the landscape of calculation.
The researchers who call oracles work in a sub -field of computer science called Computational Complexity theory. They are concerned about the inherent problems of problems, such as determining whether a number is prima or to find the shortest path between two points in a network. Some problems are easy to solve, others look much harder, but have solutions that are easy to check, while others are easy for quantum computers, but seemingly difficult for ordinary.
Complexity theorists want to understand whether these apparent differences in trouble are fundamental. Is there anything intrinsically hard about certain problems, or are we just not smart enough to come up with a good solution? Researchers address such questions by sorting problems in ‘complexity classes’-all the easy problems that are in one class, and all the problems that are easy to check are in another and proof that it is statements about the relationships Between those classes.
Unfortunately, the mapping of the landscape of calculation problems seems to be, well, difficult. So in the mid -1970s, some researchers began to study what would happen if the calculation rules were different. This is where oracles come in.
Like magic 8 balls, oracles are devices that immediately answer yes-or-no questions without revealing anything about their inner operation. Unlike magic 8 balls, they always say yes or no, and they are always correct – an advantage that it is fictional. In addition, any given Oracle will answer only a specific kind of question, such as “Is this number prime?”
What makes these fictional devices useful to understand the real world? In short, they can reveal hidden connections between different complexity classes.
Take the two most famous complexity classes. There are the class problems that are easy to solve, which researchers call ‘p’, and the class of problems that are easy to check, which researchers call np ‘. Is it easy to solve easily? If so, it would mean that NP would be equal to P, and that all coding would be easy to crack (among other consequences). Complexity theorists suspect that NP is not equal to P, but that they cannot prove it, although they have been trying to determine the relationship between the two classes for more than 50 years.
Oracles helped them understand better what they are working with. Researchers have invented oracles that answer questions that help solve many different problems. In a world where each computer had a lightning on one of these oracles, all problems that are easy to check would also be easily solved, and P equals NP. But other, less useful oracles have the opposite effect. In a world populated by these oracles, P and NP appear to be different.