<p>Informally, we say that a Turing machine $M(\cdot)$ <em>approximates</em> a function $f(\cdot)$ if their outputs on a series of inputs are <em>indistinguishable</em>.</p>

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

<p>$|\Pr[D_n(M(x))=1] - \Pr[D_n(f(x))=1]|$</p>

<p>is <em>negligible</em>, i.e. a positive quantity smaller than the reciprocal of <strong>any</strong> positive polynomial (For instance, $2^{-n}$ and $n^{-\log n}$ are negligible, but $1 \over 2$ and $n^{-2}$ are not.) Here, $n=|x|$.</p>

<hr>

<p>Since $D_n$ receives an advice, there are tests which $D_n$ can perform but $M(x)$ cannot. </p>

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

<p>The formalization follows:</p>

<p>Assume the following:</p>

<ol>
<li>$L$ is a decidable language;</li>
<li>$f$ is a polynomially bounded function;</li>
<li>$M$ is an oracle PPT Turing machine;</li>
<li>$D = \{D_k\}$ is a family of polynomial-size binary circuits.</li>
<li>$x \in L$</li>
</ol>

<p>$L$, $f$, $M$, $D$, and $x$ are selected in the given order; so, for example, $D$ may depend on $M$ but <strong>not</strong> vice versa. Let $n$ denote the size of $x$.</p>

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

<p>The question is,</p>

<blockquote>
  <p>Does there exist a decidable language $L$, and a poly-bounded function $f$, such that any PPT machine $M&#39;$ 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:</p>
  
  <p>$|\Pr[D_n(M^{D_n}(x))=1] - \Pr[D_n(f(x))=1]|$</p>
</blockquote>

<p>Moreover:</p>

<blockquote>
  <p>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:</p>
  
  <p>$|\Pr[D_n(M(\langle D_n \rangle, x)=1] - \Pr[D_n(f(x))=1]|$</p>
</blockquote>

CC BY-SA 2.5
2011-02-08T10:56:00.333Z
Well, the title is so bad. Suggestions are welcome.
Sadeq Dousti
CC BY-SA 2.5
2011-02-08T11:39:56.510Z
I'm a little confused. What are the semantics of "$S(x)$" and "$S(x,\langle D_n \rangle)$", when $S$ is a PPT machine with an oracle? What do you want the oracle queries to return when there is no oracle to query?
Ryan Williams
CC BY-SA 2.5
2011-02-08T12:14:36.537Z
@Kaveh: I tried hard but didn't get what you mean. Could you please elaborate? @Ryan: You're right. One may assume that in such cases, $S$ is equipped with an oracle which for all queries, returns a special "NULL" symbol. Moreover, observe that for the second part of the question, S need not be a query machine. (When comparing $S(x)$ and $S(x,\langle D_n \rangle)$.)
Sadeq Dousti
CC BY-SA 2.5
2011-02-08T12:36:39.330Z
Is D acting like a "Distinguisher"? What do you mean by assuming oracle access to the same machine that is going to distinguish it? Can you provide me with the idea where this question is risen? BTW, sorry to ask this preliminary question but is noticeable defined to be 1-negligible, in that case how $n^{-2}$ can be noticeable?
Yasser Sobhdel
CC BY-SA 2.5
2011-02-08T13:11:22.497Z
@Yasser: 1) You're confusing noticeable with overwhelming. 2) D can be interpreted as a distinguisher. 3) This is arisen from a research in progress. 4) In the proof of undecidability of the HALTING problem, you can see an example of such a self-referential machines (similar, but not exactly the same as here). @Kaveh: Oops, you're right. I tried to simplify the original problem, but it seems that I left out important parts. Please check the new formulation.
Sadeq Dousti
CC BY-SA 2.5
2011-02-08T15:32:08.527Z
Thanks for the explanation. :) (I removed my previous comments as they do not apply to the newer version.)
Kaveh
CC BY-SA 2.5
2011-02-08T19:13:33.540Z
@Kaveh: Thanks to you! The question at least makes sense now :)
Sadeq Dousti
CC BY-SA 2.5
2011-02-09T23:39:33.453Z
I cannot understand the very last sentence of the question.  If f is poly-time computable, isn’t it trivially poly-time approximable?
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-09T23:43:18.397Z
Can D depend on x?  If so, I do not know what it means for D to be polynomial size.  If not, it seems to me that your definition of approximability is really about approximating the probability distribution generated by applying f to the uniform bit string, not approximating the function f.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-10T12:23:00.077Z
@Tsuyoshi: Thanks a lot! I removed the part where it says $f$ is poly-time computable. Moreover, I exchanged the quantifiers over $D$ and $x$. Now it makes sense.
Sadeq Dousti
CC BY-SA 2.5
2011-02-11T01:11:36.040Z
Sadeq, I can't understand $D_n(f(x))$: if $D_n$ has $n$ inputs shouldn't it be $D_{|f(x)|}(f(x))$?
Marcus Ritt
CC BY-SA 2.5
2011-02-11T10:20:23.847Z
@Marcus: There are various definitions for the circuit model. In the one I used, $D_n$ means a circuit with $poly(n)$ bit inputs and size $poly(n)$. That is, the subscript $n$ is not the size of input itself.
Sadeq Dousti
<cc.complexity-theory><pr.probability><advice-and-nonuniformity>
Beating Nonuniformity by Oracle Access
Sadeq Dousti
# Beating Nonuniformity by Oracle Access

(Asked by: username_0 on 2011-02-08)

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:

1. $L$ is a decidable language;
2. $f$ is a polynomially bounded function;
3. $M$ is an oracle PPT Turing machine;
4. $D = \{D\_k\}$ is a family of polynomial-size binary circuits.
5. $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]|$

**Tags:** cc.complexity-theory, pr.probability, advice-and-nonuniformity

> **Comments:**
> **username_0**: Well, the title is so bad. Suggestions are welcome.  
> **username_1**: I'm a little confused. What are the semantics of "$S(x)$" and "$S(x,\langle D_n \rangle)$", when $S$ is a PPT machine with an oracle? What do you want the oracle queries to return when there is no oracle to query?  
> **username_0**: @username_3: I tried hard but didn't get what you mean. Could you please elaborate? @Ryan: You're right. One may assume that in such cases, $S$ is equipped with an oracle which for all queries, returns a special "NULL" symbol. Moreover, observe that for the second part of the question, S need not be a query machine. (When comparing $S(x)$ and $S(x,\langle D_n \rangle)$.)  
> **username_2**: Is D acting like a "Distinguisher"? What do you mean by assuming oracle access to the same machine that is going to distinguish it? Can you provide me with the idea where this question is risen? BTW, sorry to ask this preliminary question but is noticeable defined to be 1-negligible, in that case how $n^{-2}$ can be noticeable?  
> **username_0**: @Yasser: 1) You're confusing noticeable with overwhelming. 2) D can be interpreted as a distinguisher. 3) This is arisen from a research in progress. 4) In the proof of undecidability of the HALTING problem, you can see an example of such a self-referential machines (similar, but not exactly the same as here). @username_3: Oops, you're right. I tried to simplify the original problem, but it seems that I left out important parts. Please check the new formulation.  
> **username_3**: Thanks for the explanation. :) (I removed my previous comments as they do not apply to the newer version.)  
> **username_0**: @username_3: Thanks to you! The question at least makes sense now :)  
> **username_4**: I cannot understand the very last sentence of the question.  If f is poly-time computable, isn’t it trivially poly-time approximable?  
> **username_4**: Can D depend on x?  If so, I do not know what it means for D to be polynomial size.  If not, it seems to me that your definition of approximability is really about approximating the probability distribution generated by applying f to the uniform bit string, not approximating the function f.  
> **username_0**: @Tsuyoshi: Thanks a lot! I removed the part where it says $f$ is poly-time computable. Moreover, I exchanged the quantifiers over $D$ and $x$. Now it makes sense.  
> **username_5**: Sadeq, I can't understand $D_n(f(x))$: if $D_n$ has $n$ inputs shouldn't it be $D_{|f(x)|}(f(x))$?  
> **username_0**: @Marcus: There are various definitions for the circuit model. In the one I used, $D_n$ means a circuit with $poly(n)$ bit inputs and size $poly(n)$. That is, the subscript $n$ is not the size of input itself.  

---

## 0 answers

