super-natural

Natural proof

In computational complexity theory, a natural proof is a notion used to describe a class of proofs for proving lower bounds on the circuit complexity of a boolean function. 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. .

The proofs which natural proofs describe show, either directly or indirectly, that a boolean function has a certain natural combinatorial property. Under the assumption that one-way 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 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 (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, 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 C if every sequence of boolean functions having the property defines a language outside of C.

Razborov and Rudich give a number of examples of lower-bound proofs against classes C smaller than P/poly that can be "naturalized", i.e. converted into natural proofs. An important example treats proofs that the parity problem is not in the class AC⁰. They give strong evidence that the techniques used in these proofs cannot be extended to show stronger lower bounds. In particular, AC⁰-natural proofs cannot be useful against AC⁰[m]

Razborov and Rudich also demonstrate unconditionally that natural proofs cannot prove exponential lower bounds for the discrete logarithm problem.

There is strong current belief that the mechanism of this paper actually blocks lower-bound proofs against the complexity class TC⁰ of constant-depth, polynomial-sized threshold circuits, which is believed but not proven smaller than P/poly. However, some researchers believe that the Razborov-Rudich limitations are actually good guidance for what a "super-natural" lower-bound proof might involve, such as properties hard or complete for exponential space.