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.