# Is there some mathematical properties of the distribution which is the output of a probabilistic polynomial-time Turing machine?

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]$.

• It seems obvious that you can pick $S_n$ and $A$ such that you can pretty much obtain any (computable) $f \in F$. – Raphael Dec 7 '17 at 11:14
• The way you defined it, $d=0$. – Ariel Dec 7 '17 at 13:52
• $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). – Ariel Dec 7 '17 at 17:17
• 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)$. – 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$.