Computer scientists are using hypothetical devices called “oracles” to advance the field of computational complexity theory, exploring fundamental questions about problem-solving difficulty. These theoretical tools, which instantly provide correct yes-or-no answers to specific questions, help researchers understand relationships between different classes of computational problems.

Oracles have proved particularly valuable in studying quantum computing, leading to breakthroughs like Peter Shor’s 1994 quantum algorithm for factoring large numbers. The technique has also helped researchers rule out certain approaches to solving the longstanding P versus NP problem, a central question in computer science.