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$ – David Richerby Mar 18 '15 at 15:02
  • $\begingroup$ ...but the answer below is a much clearer entry to the concept than the wikipedia article or its introduction. $\endgroup$ – Joshua Goldberg Oct 27 '17 at 23:31

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$ – Yuval Filmus May 4 '18 at 10:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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