<p>If $G: \{0,1\}^k \rightarrow \{0,1\}^{2k}$ is a polynomial time computable pseudorandom generator with security $t(k)$, that is such that every adversary running in time $\leq t(k)$ has distinguishing probability $\leq 1/t(k)$, then we can construct a family of functions $f: \{0,1\}^n \rightarrow \{0,1\}$ such that each function is computable by circuit of size $k(n)^c$, where $c$ is an absolute constant, but the truth-table of a random function from the family is indistinguishable from the truth-table of a truly random function by properties computable in time roughly $t(k(n))$, where we are free to choose $k(n)$ any way we want. Such a family of function contradicts the existence of a natural property computable in time $t(k(n))$ and useful against circuits of size $k(n)^c$.</p>

<p>Now it is a matter to instantiate the parameters. If we believe that there are one-way functions secure against sub-exponential adversaries, then we can take $t(k) = 2^{k^{\epsilon}}$ for an absolute constant $\epsilon &gt;0$. If there were a quasi-polytime natural property that is useful against size($n^e$) for every $e$, then we can take $k(n)= n^{e}$ for every $e$, and the property would still be able to distinguish  our family of functions computed by circuits of size $n^{ce}$ from truly random functions, even though no property computable in time $\leq t(k(n)) = 2^{n^{\epsilon e}}$ can do that. This quasi-polytime computable property is computable in time $\leq 2^{n^d}$ for some absolute constant $d$, and we reach a contradiction when $e &gt; d/\epsilon$. (Recall that $d,\epsilon$ are absolute constants and that we can take $e$ as large as we want.)</p>

<p>The point here is the order of quantifiers. If you are looking for a specific polynomial circuit size, like $n^{10}$, you can have a quasi-polytime natural property that is useful against those circuits, because you can actually explicitly check in time roughly $2^{n^{10}}$ if a given function is computable by a circuit of size $n^{10}$. If, however, you want a quasy-polytime natural property that is simultaneously useful against all circuit sizes $n^e$ for all $e$ (that is, for each $e$, the property becomes useful after a sufficiently large $n$), then you are impyling the existence of sub-exponential distinguishers for pseduroandom generators and sub-exponential inverters for one-way functions.</p>

CC BY-SA 2.5
2011-02-19T20:11:02.937Z
2011-02-19T20:11:02.937Z
Luca Trevisan
<p>The Natural Proof theorem says :</p>

<ul>
<li>If for a fixed $c&gt;1$ $G_k \in SIZE(k^c)$ is $2^{k^\epsilon}$-hard then not exists a $quasiP$-Natural Property that for all $e$ sufficently large is usefull against $SIZE(n^e)$.</li>
</ul>

<p>The idea in the proof is that if you can distinguish a random function from a function in $SIZE(n^e)$ you can invert a pseudorandom generator. $SIZE(n^e)$ is big enough to compute pseudorandom function generator (based on the pseudorandom string generator $G_k$)</p>

<p>can we say that?</p>

<ul>
<li>If for any k,n (where if we fix n then we can choose any $k=n^{O(1)}$) $G:\{0,1\}^k\times \{0,1\}^n \rightarrow \{0,1\}$ is a pseudorandom functions genereator (for a sub-exponential adversaries) computable in $SIZE(n^e)$ then not exists a $quasiP$-Natural Property usefull against $SIZE(n^e)$.</li>
</ul>

<p>I think that it's wrong, because for any fixed $e$ you can find a $quasiP$-Natural Property against $SIZE(n^e)$. But I can't see why</p>

CC BY-SA 2.5
2011-02-15T16:58:17.847Z
The order of quantifiers should be for every quasiP-time computable natural property and for every sufficiently large e  ...
Luca Trevisan
CC BY-SA 2.5
2011-02-15T17:17:58.487Z
this questions appears hopelessly misformatted: can someone who understands the question try to redo it ?
Suresh Venkat
CC BY-SA 2.5
2011-02-17T14:56:50.000Z
I'm sorry, I'm trying to redo it!,
AntonioFa
<cc.complexity-theory><natural-proofs>
quasiP-Natural Property again SIZE($n^e$) for fixed e.
AntonioFa
# quasiP-Natural Property again SIZE($n^e$) for fixed e.

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

The Natural Proof theorem says :

* If for a fixed $c>1$ $G\_k \in SIZE(k^c)$ is $2^{k^\epsilon}$-hard then not exists a $quasiP$-Natural Property that for all $e$ sufficently large is usefull against $SIZE(n^e)$.

The idea in the proof is that if you can distinguish a random function from a function in $SIZE(n^e)$ you can invert a pseudorandom generator. $SIZE(n^e)$ is big enough to compute pseudorandom function generator (based on the pseudorandom string generator $G\_k$)

can we say that?

* If for any k,n (where if we fix n then we can choose any $k=n^{O(1)}$) $G:\{0,1\}^k\times \{0,1\}^n \rightarrow \{0,1\}$ is a pseudorandom functions genereator (for a sub-exponential adversaries) computable in $SIZE(n^e)$ then not exists a $quasiP$-Natural Property usefull against $SIZE(n^e)$.

I think that it's wrong, because for any fixed $e$ you can find a $quasiP$-Natural Property against $SIZE(n^e)$. But I can't see why

**Tags:** cc.complexity-theory, natural-proofs
> **Comments:**
> **username_1**: The order of quantifiers should be for every quasiP-time computable natural property and for every sufficiently large e  ...  
> **username_2**: this questions appears hopelessly misformatted: can someone who understands the question try to redo it ?  
> **username_0**: I'm sorry, I'm trying to redo it!,  

---

## 1 answers

### Answer by username_1 on 2011-02-19. Score: 5 | Accepted answer

If $G: \{0,1\}^k \rightarrow \{0,1\}^{2k}$ is a polynomial time computable pseudorandom generator with security $t(k)$, that is such that every adversary running in time $\leq t(k)$ has distinguishing probability $\leq 1/t(k)$, then we can construct a family of functions $f: \{0,1\}^n \rightarrow \{0,1\}$ such that each function is computable by circuit of size $k(n)^c$, where $c$ is an absolute constant, but the truth-table of a random function from the family is indistinguishable from the truth-table of a truly random function by properties computable in time roughly $t(k(n))$, where we are free to choose $k(n)$ any way we want. Such a family of function contradicts the existence of a natural property computable in time $t(k(n))$ and useful against circuits of size $k(n)^c$.

Now it is a matter to instantiate the parameters. If we believe that there are one-way functions secure against sub-exponential adversaries, then we can take $t(k) = 2^{k^{\epsilon}}$ for an absolute constant $\epsilon >0$. If there were a quasi-polytime natural property that is useful against size($n^e$) for every $e$, then we can take $k(n)= n^{e}$ for every $e$, and the property would still be able to distinguish our family of functions computed by circuits of size $n^{ce}$ from truly random functions, even though no property computable in time $\leq t(k(n)) = 2^{n^{\epsilon e}}$ can do that. This quasi-polytime computable property is computable in time $\leq 2^{n^d}$ for some absolute constant $d$, and we reach a contradiction when $e > d/\epsilon$. (Recall that $d,\epsilon$ are absolute constants and that we can take $e$ as large as we want.)

The point here is the order of quantifiers. If you are looking for a specific polynomial circuit size, like $n^{10}$, you can have a quasi-polytime natural property that is useful against those circuits, because you can actually explicitly check in time roughly $2^{n^{10}}$ if a given function is computable by a circuit of size $n^{10}$. If, however, you want a quasy-polytime natural property that is simultaneously useful against all circuit sizes $n^e$ for all $e$ (that is, for each $e$, the property becomes useful after a sufficiently large $n$), then you are impyling the existence of sub-exponential distinguishers for pseduroandom generators and sub-exponential inverters for one-way functions.


---

