In the traditional oracle Turing machine, the oracle is specified as a decision problem. Roughly speaking, one puts a string in the oracle tape, and asks whether it is true or false.

I am wondering whether it makes sense to consider a functional oracle. This means, one puts a string $x$ in the oracle tape, and guarantee the returned result $f(x)$ is polynomially bounded in length by $x$, and the oracle is supposed to return $f(x)$.

A very natural such an oracle is an FNP oracle, and one can define a class $P^{FNP}$.

Any study regarding this? Or the notion is not well defined? Any comments are welcome.

  • $\begingroup$ @Marzio having a function oracle might make a difference if the oracle access is somehow restricted, e.g. if only a bounded (sub-linear) number of queries are possible or if queries are non-adaptive. $\endgroup$ Oct 8 '15 at 16:17
  • $\begingroup$ @JanJohannsen: you're right ... I deleted the inaccurate quick comment. $\endgroup$ Oct 8 '15 at 16:24
  • 4
    $\begingroup$ Yes, they are quite common. You can even use search problems as oracles. Google for P^NP[wit] or for "witness-oracle". $\endgroup$
    – Kaveh
    Oct 8 '15 at 22:02
  • 3
    $\begingroup$ Functional oracles are also widely used in higher-order complexity. For instance, the class of second order basic feasible functionals ($\mathsf{BFF}_2$) may be defined in terms of oracle Turing machines, once a suitable notion of size of a function $\{0,1\}^\ast\to\{0,1\}^\ast$ is given. See for instance this nice survey paper (the definition of oracle Turing machine is in Sect. 6). $\endgroup$ Oct 9 '15 at 9:01

Your Answer

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

Browse other questions tagged or ask your own question.