Natural proof
From Wikipedia, the free encyclopedia
In computational complexity theory, a natural proof is a notion introduced by Alexander Razborov and Steven Rudich to describe a class of proofs for proving lower bounds on the circuit complexity of a boolean function. The proofs they describe show, either directly or indirectly, that a boolean function has a certain natural combinatorial property. Under the assumption that one-way functions exist, Razborov and Rudich show that these proofs cannot separate certain complexity classes. Notably, assuming one-way functions exist, these proofs cannot separate the complexity classes P and NP.
For example, 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."
A property is natural if it meets the constructivity and largeness conditions defined by Razborov and Rudich. Roughly speaking, the constructivity condition requires that a property be decidable in polynomial time when the truth table of a boolean function is given as input. Properties that are easy to understand are likely to satisfy this condition, so simple proof techniques will probably not resolve the P vs. NP question. The largeness condition requires that the property hold for a sufficiently large number of the set of all boolean functions.
A property is useful against a complexity class, P/poly in the paper, if any sequence of functions having the property do not belong to that complexity class.
Razborov and Rudich give a number of examples of lower-bound proofs that naturalize: for example, the proof that the parity problem is not in the complexity class AC0. This is strong evidence that the techniques used in these proofs cannot be extended to show stronger lower bounds. In particular, AC0-natural proofs cannot be useful against AC0[m].
Razborov and Rudich also demonstrate unconditionally that natural proofs cannot prove exponential lower bounds for the discrete logarithm problem.
[edit] References
- 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
- Feasible Proofs and Computations
