Why Computer Scientists Need Magic 8 Ball-Like Oracles
1 min read
Summary
Scientists who work in computational complexity theory use hypothetical devices called oracles to help understand the intrinsic difficulty of computational problems, and to develop new algorithms.
Oracles are thought experiments, and always give a yes or a no to any question, providing a useful tool for researchers who want to understand the real-world behaviour of computers.
Unlike a real magic 8 ball, an oracle will only answer a specific type of question, such as whether a given number is prime.
By inventing new oracles, scientists can reveal hidden connections between different complexity classes, helping them to answer fundamental questions about the relationship between different types of problems.
Oracle experiments have helped complexity theorists to better understand the P versus NP problem, and the potential power of quantum computers.