The common understanding of what oracle does is that it answers a question after a single operation. So at first glance, it runs in $O(1)$. But, doesn't it need to actually read the input? Wouldn't this take at least $n$ steps? If so then wouldn't an oracle run in $O(n)$?

  • 1
    $\begingroup$ The common answer is "zero" time to compute the answer but of course writing the query to the oracle takes time. $\endgroup$ – Ryan Jun 30 '16 at 23:43
  • $\begingroup$ So conceptually it is meant to be used like: oracle.setInput1(a), oracle.setInput2(b), oracle.setInput3(b), bool answer = oracle.solve() $\endgroup$ – C Shreve Jul 1 '16 at 0:13
  • $\begingroup$ Something like that? $\endgroup$ – C Shreve Jul 1 '16 at 1:12
  • $\begingroup$ Check any proof that uses an oracle machine. What do they do? $\endgroup$ – Raphael Jul 1 '16 at 7:46

The oracle runs in a single step. Yes, it would take an ordinary Turing machine some number of steps to read the input but an oracle isn't an ordinary Turing machine – that's almost the whole point of using them. Also, the time taken for the oracle to read its input is essentially accounted for by the time it took the calling machine to write that input. So, oracles return in $O(1)$ steps. More precisely, they return in exactly one step.

Also, it's not quite clear what you mean by "$O(n)$ steps". $n$ usually denotes the length of the input we're trying to compute on, which would be the input to the calling machine, not the oracle. The input to the oracle could be arbitrarily long. For example, you could have a machine that takes an input $x$ and calls an oracle to ask if the string consisting of $2^{2^{2^{|x|}}}$ zeroes is in the language decided by the oracle. Moral of the tale: don't write functions of $n$ without saying what $n$ is.

  • $\begingroup$ What if the oracle erases its input upon invocation? In that case, it does (effectively) take $O(n)$ steps. $\endgroup$ – Yuval Filmus Jul 1 '16 at 13:44
  • $\begingroup$ @YuvalFilmus It's defined to take one step. $\endgroup$ – David Richerby Jul 1 '16 at 14:09
  • $\begingroup$ Right, but an $O(n)$ oracle is equivalent to an $O(1)$ oracle which erases its input (assuming reasonable time and space constraints, and a multi-tape Turing machine). $\endgroup$ – Yuval Filmus Jul 1 '16 at 14:14

The time it takes the oracle doesn't matter. The oracle gives you a hint that you can use to determine the answer that you want. You will still need to check that hint, that is you need to write a program that accepts the original input, and the hint, and which in polynomial time outputs "Yes" if the the answer to the original question is "Yes" and the hint is useful. This will typically involve reading the input and the hint.

The oracle doesn't solve the problem. It just gives you a hint. We look at problems where we can prove the existence of a good hint. (For example, to solve the travelling salesman a tour that supposedly solves the problem is a hint, but we need to check that it actually does solve it).

  • 1
    $\begingroup$ This is incorrect. An oracle for a language $L$ solves the membership problem for a language $L$. That is all it does. $\endgroup$ – David Richerby Jul 1 '16 at 10:53
  • $\begingroup$ If the oracle takes a long time, then that matters. Also, a Turing Machine with an oracle for a language $L$ could solve $L$ very quickly, because the 'hint' is really the answer. And whether you need to output in polynomial time depends on whether that is being asked. $\endgroup$ – Lieuwe Vinkhuijzen Jul 1 '16 at 12:52
  • $\begingroup$ What you're describing is just one of many possible oracles, and it isn't relevant here. $\endgroup$ – Gilles 'SO- stop being evil' Jul 1 '16 at 16:40

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.