Natural Proof: Distinguish Simple From Random
In this post, we briefly give an overview of the famous “natural proof barrier” [RR94], which explained why it's extremely hard to obtain a circuit lower bound towards the P vs. NP problem.
The content of this post has its reference mainly from the book [AB09], rather than the original paper [RR94].
Introduction
The celebrated natural proof theorem, stated by Razborov and Rudich in [RR94], gives the fundamental limitation of the common proof technique that has the following form:
- all circuits of size \(s\) do not satisfy some certain property \(\mathcal{P}\) (which is “not simple”, i.e., having a size lower bound \(s\)),
- the target function \(f\) satisfies the property \(\mathcal{P}\),
- so \(f\) has the size lower bound \(s\).