Natural proof
Encyclopedia
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 one-way function
s) 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 one-way function
s 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:
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 2n-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.
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 AC0
. They give 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 reproduce Avi Wigderson's unconditional proof 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 TC0
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.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, a natural proof is a certain kind of proof establishing that one complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
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 one-way function
One-way function
In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here "easy" and "hard" are to be understood in the sense of computational complexity theory, specifically the theory of polynomial time problems...
s) 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
Alexander Razborov
Aleksandr Aleksandrovich Razborov , sometimes known as Sasha Razborov, is a Soviet and Russian mathematician and computational theorist who won the Nevanlinna Prize in 1990 for introducing the "approximation method" in proving Boolean circuit lower bounds of some essential algorithmic problems, and...
and Steven Rudich
Steven Rudich
Steven Rudich is a professor in the Carnegie Mellon School of Computer Science. In 1994, he and Alexander Razborov proved that a large class of combinatorial arguments, dubbed natural proofs were unlikely to answer many of the important problems in computational complexity theory. For this work,...
in their article Natural proofs, first presented in 1994, and later published in 1997, for which they received the 2007 Gödel Prize
Gödel Prize
The Gödel Prize is a prize for outstanding papers in theoretical computer science, named after Kurt Gödel and awarded jointly by the European Association for Theoretical Computer Science and the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory .The...
.
Specifically, natural proofs prove lower bounds on the circuit complexity
Circuit complexity
In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of Boolean circuits that compute them....
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 one-way function
One-way function
In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here "easy" and "hard" are to be understood in the sense of computational complexity theory, specifically the theory of polynomial time problems...
s 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 SATBoolean satisfiability problemIn computer science, satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE...
, 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 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 2n-sized truth table
Truth table
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—to compute the functional values of logical expressions on each of their functional arguments, that is, on each combination of values taken by their...
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.
Razborov and Rudich give a number of examples of lower-bound proofs against classes C smaller than P/poly
P/poly
In computational complexity theory, P/poly is the complexity class of languages recognized by a polynomial-time Turing machine with a polynomial-bounded advice function. It is also equivalently defined as the class PSIZE of languages that have a polynomial-size circuits...
that can be "naturalized", i.e. converted into natural proofs. An important example treats proofs that the parity problem is not in the class AC0
AC0
AC0 is a complexity class used in circuit complexity. It is the smallest class in the AC hierarchy, and consists of all families of circuits of depth O and polynomial size, with unlimited-fanin AND gates and OR gates....
. They give 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
Razborov and Rudich also reproduce Avi Wigderson's unconditional proof 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 TC0
TC0
TC0 is a complexity class used in circuit complexity. It is the first class in the hierarchy of TC classes.TC0 contains all languages which are decided by Boolean circuits with constant depth and polynomial size, containing only unbounded-fanin AND gates, OR gates, and majority gates...
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.