MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The famous "Natural Proof" paper , , ‎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

enter image description here

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.

Could anyone give some guidance about this point?


share|cite|improve this question
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
Thanks,Done.Details added. – Hao Yu Dec 15 '13 at 1:03

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.