Let $S_{n}$ be an input set whose elements are length $n$, namely $S_{n} = \Sigma^{n}$. For every probabilistic polynomial-time algorithm $A$ and any $u \in \Sigma^{*}$, there exists a function $f^{A}$ such that $f^A(u) = \mathrm{Pr}[A(u) = 1]$. And let $f^{A}_{n} = \left.f^{A}\right\vert_{S_{n}}$ be a function from $S_{n}$ to $[0,1]$.

Is there some properties about what $f^A_n$ looks like? Or is there some references that introduce about this?

Indeed, let $F_{n} = \{ f^{A}_n \mid A \text{ is a PPT algorithm} \}$. And if we define $$\mathrm{Dist}_{n}(f^{A},f^{B}) = \sum_{u \in S_{n}} \left\vert f^{A}(u) - f^{B}(u)\right\vert$$ and $$d_{1}(n) = \inf \{ \mathrm{Dist}_{n}(f^{A},f^{B}) \mid f^{A} \neq f^{B} \}$$ how does $d(n)$ grow?

How about $$d_{2}(n) = \sup_{g} \inf_{A} \mathrm{Dist}_{n}(f^{A},g)$$ where $g$ is a function from $\Sigma^{*}$ to $[0,1]$.

  • $\begingroup$ It seems obvious that you can pick $S_n$ and $A$ such that you can pretty much obtain any (computable) $f \in F$. $\endgroup$ – Raphael Dec 7 '17 at 11:14
  • $\begingroup$ The way you defined it, $d=0$. $\endgroup$ – Ariel Dec 7 '17 at 13:52
  • $\begingroup$ $d_1(n)$ is not a very interesting measure, you could always perturb the acceptance probability slightly on some input, so you have something like $d_1(n)\le 2^{-n^c}$ for all $c\in\mathbb{N}$ (assuming both $A,B$ are polynomial time). $\endgroup$ – Ariel Dec 7 '17 at 17:17
  • $\begingroup$ Note that the definition of $d_2$ is also problematic, since you allow different algorithms $A$ for each length $n$, and this suffers from the same issues raised by Raphael (you can get arbitrarily close to $g$ for each value of $n$ separately). I interpreted your questions as follows: given $g$, find a lower bound $B(n)$ such that for all probabilistic polynomial algorithms $A$: $Dist_n(f^A,g)=\Omega (B)$. $\endgroup$ – Ariel Dec 7 '17 at 17:31

Given a probabilistic algorithm $A$, define $f^A(x)=\Pr[A(x)=1]$. To make the question interesting, you have to ask whether $f^A$ (with polynomial $A$) can be close to $g$, for infinitely many values of $n$. Otherwise, as Raphael mentioned, you can pretty much obtain any $g:\Sigma^n\rightarrow [0,1]$, while keeping $A$ polynomial (there is no asymptotics). Consider the problem of how $dist_n(f^A,g)=\sum\limits_{x\in S^n}\left|g(x)-f^A(x)\right|$ grows as a function of $n$. Obviously $dist_n(f,g)\le 2^n$, and a random guessing $A$ achieves $dist_n(f^A,g)\le 2^{n-1}$, can we find a probabilistic polynomial algorithm $A$ such that $dist_n$ grows polynomialy?

Let $L\subseteq\Sigma^*$ be some language, and $f^L:\Sigma^*\rightarrow \{0,1\}$ be its indicator function, i.e. $f^L(x)=1\iff x\in L$. If for large enough $n$ it holds that $\sup\limits_{x\in\Sigma^n}\left|f^L(x)-f^A(x)\right|\le\frac{1}{2}-\epsilon$, then $\mathsf{L\in BPP}$ (simulate $A$ several times and take the majority vote, this works for $\epsilon=n^{-d}$). If for large enough $n$ you have $\sum\limits_{x\in\Sigma^n}\left|f^L(x)-f^A(x)\right|\le poly(n)$, then $\mathsf{L\in P/Poly}$, since your advice can contain information about all strings $x\in\Sigma^n$ on which $f^L,f^A$ differ by more than (say) $\frac{1}{3}$, and on the rest of the strings you can take the majority vote as above.

Thus, to answer your question, if $g$ is an indicator function for a hard language, you can expect (under some hardness assumptions) that there is no probabilistic polynomial time algorithm $A$ for which $Dist_n(f^A,g)$ is polynomial in $n$.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.