Hypothetical devices that can quickly and accurately answer questions have become a powerful tool in computational complexity theory.

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.

...read more at quantamagazine.org