# About “natural proof” of Razborov and Rudich

The famous "Natural Proof" paper ,http://www.cs.umd.edu/~gasarch/BLOGPAPERS/natural.pdf , ‎of Razborov and Rudich gives a barrier for any proof that try to separate P and NP. It mainly shows that if there is a high enough "hard" pseudo-randomness generator then there is no "natural proof" that can give the super-polynomial lower bounds of circuit complexity for any problem. The rigorous statement is as follows:

I don't understand the final part of the proof of Razborov and Rudich's 'natural proof'. I use Timothy Chow's paper 'Almost natural proof". The argument goes as follows

It is essentially the same as the proof of Razborov and Rudich. You can simply ignore the slightly modified part. It says " we obtain a statistical test that distinguishes between $G_k(x(u))$ and $(x(u'),x(u''))$", but actually, for $G_k(x(u))$, we obtained our function$f_i$ as described in the proof, but for$(x(u'),x(u''))$ we have to firstly transform it into $(G_k(x(u')),G_k(x(u'')))$, then construct a function $f_{i-1 }$ as in the proof, then use $C_n$. In other words, we don't formally have the same construction for $(x(u'),x(u''))$ as $(G_k(x(u))$. So even if they use the same $C_n$, but the construction from $G_k(x(u))$ to function $f_i$ and the construction from $(x(u'),x(u''))$ to function$f_{i-1}$ are completely different, so finally they actually use different circuits.

You should state the theorem whose proof you're asking about. Also, use the appropriate markup to render mathematical expressions, e.g. instead of f_(i-1) do $f_{i-1}$. –  Amit Kumar Gupta Dec 14 '13 at 18:12