Natural proof

In computational complexity theory, a natural proof is a certain kind of proof establishing that one complexity class differs from another one. While these proofs are in some sense "natural", it can be shown (assuming a widely believed conjecture on the existence of pseudorandom functions) that no such proof can possibly be used to solve the P vs. NP problem.

The notion of natural proofs was introduced by Alexander Razborov and Steven Rudich in their article "Natural Proofs", first presented in 1994, and later published in 1997, for which they received the 2007 Gödel Prize.

Specifically, natural proofs prove lower bounds on the circuit complexity of boolean functions. A natural proof shows, either directly or indirectly, that a boolean function has a certain natural combinatorial property. Under the assumption that pseudorandom functions exist with "exponential hardness" as specified in their main theorem, Razborov and Rudich show that these proofs cannot separate certain complexity classes. Notably, assuming pseudorandom functions exist, these proofs cannot separate the complexity classes P and NP.

For example, their article states:

A property of boolean functions is defined to be natural if it contains a property meeting the constructivity and largeness conditions defined by Razborov and Rudich. Roughly speaking, the constructivity condition requires that a property be decidable in (quasi-)polynomial time when the 2ⁿ-sized truth table of an n-input boolean function is given as input, asymptotically as n increases. This is the same as time singly exponential in n. Properties that are easy to understand are likely to satisfy this condition. The largeness condition requires that the property hold for a sufficiently large fraction of the set of all boolean functions.

A property is useful against a complexity class C if every sequence of boolean functions having the property infinitely often defines a language outside of C. A natural proof is a proof that establishes that a certain language lies outside of C and refers to a natural property that is useful against C.

...
Wikipedia