Natural proof
|
|
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 (http://citeseer.ist.psu.edu/656725.html)Template:Math-stub