Informally, we say that a Turing machine $M(\cdot)$ approximates a function $f(\cdot)$ if their outputs on a series of inputs are indistinguishable.
More formally, let $L$ be a language, $M(\cdot)$ be a probabilistic polynomial-time (PPT) Turing machine, and $f(\cdot)$ be a polynomially bounded function: $f \colon \{0,1\}^n \to \{0,1\}^{\text{poly}(n)}$. We say that $M$ approximates $f$ on $L$ if for all families of polynomial-size binary circuits $D = \{D_k\}$, and for all large enough $x \in L$, it holds that the following quantity:
$|\Pr[D_n(M(x))=1] - \Pr[D_n(f(x))=1]|$
is negligible, i.e. a positive quantity smaller than the reciprocal of any positive polynomial (For instance, $2^{-n}$ and $n^{-\log n}$ are negligible, but $1 \over 2$ and $n^{-2}$ are not.) Here, $n=|x|$.
Since $D_n$ receives an advice, there are tests which $D_n$ can perform but $M(x)$ cannot.
This question seeks the existence of functions which are not approximable in the above sense, but are approximable if $M$ has black-box or code access to $D$.
The formalization follows:
Assume the following:
- $L$ is a decidable language;
- $f$ is a polynomially bounded function;
- $M$ is an oracle PPT Turing machine;
- $D = \{D_k\}$ is a family of polynomial-size binary circuits.
- $x \in L$
$L$, $f$, $M$, $D$, and $x$ are selected in the given order; so, for example, $D$ may depend on $M$ but not vice versa. Let $n$ denote the size of $x$.
If $M$ is not explicitly equipped with an oracle, we implicitly assume that there's an oracle which for all queries, returns a special $\perp$ symbol. (Meaning that "I don't know the answer to your query.")
The question is,
Does there exist a decidable language $L$, and a poly-bounded function $f$, such that any PPT machine $M'$ fails to approximate $f$ on infinitely many $x\in L$, but there exists some PPT oracle machine $M$ such that for all poly-size circuit $D$, machine $M^{D_n}$ can approximate $f$ on $L$. That is, the following quantity is negligible:
$|\Pr[D_n(M^{D_n}(x))=1] - \Pr[D_n(f(x))=1]|$
Moreover:
What if $M$ was given an encoding of $D_n$ instead of oracle access to it? That is, what if we required that $M(\langle D_n \rangle, \cdot)$ should approximate $f(\cdot)$ on $L$? (here, $\langle D_n \rangle$ denotes the encoding of $D_n$ in some canonical way.) This means that the following quantity is negligible:
$|\Pr[D_n(M(\langle D_n \rangle, x)=1] - \Pr[D_n(f(x))=1]|$
