<p>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. </p>

<p>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)$. </p>

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

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

CC BY-SA 3.0
2015-10-08T16:17:08.530Z
@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
CC BY-SA 3.0
2015-10-08T16:24:21.663Z
@JanJohannsen: you're right ... I deleted the inaccurate quick comment.
Marzio De Biasi
CC BY-SA 3.0
2015-10-08T22:02:36.720Z
Yes, they are quite common. You can even use search problems as oracles. Google for P^NP[wit] or for "witness-oracle".
Kaveh
CC BY-SA 3.0
2015-10-09T09:01:25.697Z
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](http://www.cis.syr.edu/~royer/archive/cbff1-a4.pdf) (the definition of oracle Turing machine is in Sect. 6).
Damiano Mazza
<cc.complexity-theory><np><oracles>
Functional oracles
maomao
# Functional oracles

(Asked by: username_0 on 2015-10-08)

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.

**Tags:** cc.complexity-theory, np, oracles
> **Comments:**
> **username_1**: @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.  
> **username_2**: @JanJohannsen: you're right ... I deleted the inaccurate quick comment.  
> **username_3**: Yes, they are quite common. You can even use search problems as oracles. Google for P^NP[wit] or for "witness-oracle".  
> **username_4**: 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](http://www.cis.syr.edu/~royer/archive/cbff1-a4.pdf) (the definition of oracle Turing machine is in Sect. 6).  

---

## 0 answers

