I'm reading a paper for school and I have come across a passage that I don't understand. It says "If we allow the query to access the entries of the array through an oracle, it is possible to obtain a data structure of sublinear size".

Searching for information on what Oracle Access is has given me nothing but stuff about Oracle Databases, which is obviously not what I'm looking for. I can't really wrap my head around what this means.

Can anyone point me in the right direction?

  • 2
    $\begingroup$ I can see how that's something one would have difficulty searching for! The information you're looking for is at en.wikipedia.org/wiki/Oracle_machine $\endgroup$ Mar 18, 2015 at 15:02
  • $\begingroup$ ...but the answer below is a much clearer entry to the concept than the wikipedia article or its introduction. $\endgroup$ Oct 27, 2017 at 23:31

2 Answers 2


An oracle is basically a magic black box that does something (e.g. query the entries of an array), usually in constant time. How the oracle does this is abstracted away from (and sometimes an oracle might even do something impossible like solve the halting problem). It's just a way of saying "presume we had these computational abilities, then ...".


An oracle machine is an abstract machine which is assumed to solve a problem that might be undecidable or not yet solved.

For instance, "if we know how to solve problem A we can also solve problem B". Then we assume an "oracle" solving problem A even though we don't have a solution.

  • 1
    $\begingroup$ Oracle access is a more general concept. $\endgroup$ May 4, 2018 at 10:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.