Editing Natural proof

{{short description|Provides lower bounds on the circuit complexity of boolean functions}}
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 function family|pseudorandom functions]]) that no such proof can possibly be used to solve the [[P versus NP problem|P vs. NP problem]].

==Overview==
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]].<ref name="RRGodel2007">{{cite web|title=ACM-SIGACT 2007 Gödel Prize|url=http://www.sigact.org/Prizes/Godel/2007.html|access-date=2014-08-11|archive-url=https://web.archive.org/web/20160303173027/http://www.sigact.org/Prizes/Godel/2007.html|archive-date=2016-03-03|url-status=dead}}</ref>

Specifically, natural proofs prove lower bounds on the [[circuit complexity]] of [[boolean function]]s. 
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.<ref>{{cite journal | author = A. A. Razborov and S. Rudich | doi = 10.1006/jcss.1997.1494 | title = Natural proofs | journal =  Journal of Computer and System Sciences | volume = 55 | pages = 24–35 | year = 1997| doi-access = free }} ([http://www.mi.ras.ru/~razborov/int.ps Draft])</ref>

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 [[Boolean satisfiability problem|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.''<ref>Razborov+Rudich (1997), p.26 left</ref>

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<sup>''n''</sup>-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|AC<sup>0</sup>]].  They give strong evidence that the techniques used in these proofs cannot be extended to show stronger lower bounds. In particular, AC<sup>0</sup>-natural proofs cannot be useful against [https://complexityzoo.net/Complexity_Zoo:A#ac0m AC<sup>0</sup><nowiki>[m]</nowiki>].

Razborov and Rudich also reproduce [[Avi Wigderson]]'s unconditional proof that natural proofs cannot prove exponential lower bounds for the [[discrete logarithm#Cryptography|discrete logarithm]] problem.

There is strong current belief that the mechanism of this paper actually blocks lower-bound proofs against the complexity class [[TC0|TC<sup>0</sup>]] of constant-depth, polynomial-sized threshold circuits, which is believed but not proven smaller than P/poly.<ref>{{Cite web|url=https://complexityzoo.net/Complexity_Zoo:T#tc0|title = Complexity Zoo:T - Complexity Zoo}}</ref> This belief is because, under widely believed conjectures regarding the hardness of [[Elliptic curve cryptography|factoring in certain elliptic curve groups]], [[Naor-Reingold Pseudorandom Function|there exist]] exponentially hard pseudorandom functions computable in TC<sup>0</sup>.<ref>{{Cite journal|url=http://dl.acm.org/citation.cfm?id=972643|doi = 10.1145/972639.972643|title = Number-theoretic constructions of efficient pseudo-random functions|year = 2004|last1 = Naor|first1 = Moni|last2 = Reingold|first2 = Omer|journal = Journal of the ACM|volume = 51|issue = 2|pages = 231–262|s2cid = 8665271|url-access = subscription}}</ref> 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.<ref>{{cite journal | author = K. Regan | url = http://www.cse.buffalo.edu/~regan/papers/pdf/Reg02MSFD.pdf | title = Understanding the Mulmuley-Sohoni Approach to P vs. NP | journal = Bulletin of the European Association for Theoretical Computer Science | volume = 78 | pages = 86–97 |date=October 2002}}</ref>

==Notes==
<references/>

==References==
* {{cite book | author = A. A. Razborov | chapter = Feasible Proofs and Computations: Partnership and Fusion | title = Proceedings of the 31st ICALP | series = Lecture Notes in Computer Science | volume = 3142 | year = 2004 | pages = 8–14}} ([http://www.mi.ras.ru/~razborov/icalp_lics.ps Draft])
* {{cite web | url = http://weblog.fortnow.com/2006/05/importance-of-natural-proofs.html | title = The Importance of Natural Proofs | author = Lance Fortnow | date = 2006-05-10}}
* {{citation | first=Timothy Y. | last=Chow | title=WHAT IS... a Natural Proof? | url=https://www.ams.org/notices/201111/rtx111101586p.pdf | publisher=AMS | year=2011 | journal=Notices | volume=58 | issue=11 | accessdate=2014-08-05 }}

{{DEFAULTSORT:Natural Proof}}
[[Category:Computational complexity theory]]