# Functional oracles

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.

• @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. – Jan Johannsen Oct 8 '15 at 16:17
• @JanJohannsen: you're right ... I deleted the inaccurate quick comment. – Marzio De Biasi Oct 8 '15 at 16:24
• Yes, they are quite common. You can even use search problems as oracles. Google for P^NP[wit] or for "witness-oracle". – Kaveh Oct 8 '15 at 22:02
• 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). – Damiano Mazza Oct 9 '15 at 9:01