In computational complexity theory, natural proof is a notion introduced by Alexander Razborov and Steven Rudich , to classify the set of proofs that will fail to prove separations between complexity classes.

Among others, their article states: "(..) consider a commonly-envisioned proof strategy for proving P != NP:

• Formulate some mathematical notion of "discrepancy" or "scatter" or "variation" of the values of a Boolean function, or of an associated polytope or other structure. (..)
• Show by an inductive argument that polynomial-sized circuits can only compute functions of "low" discrepancy. (..)
• Then show that SAT, or some other function in NP, has "high" discrepancy.

Our main theorem in Section 4 gives evidence that no proof strategy along these lines can ever succeed."

Reference

• A. A. Razborov and S. Rudich. Natural proofs. In Proceedings, 26th ACM Symposium on Theory of Computing, pages 204--213, 1994
• Online version of the article