Talk:Natural proof
 | This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
| |||||||||||
My addition is based on "Natural Proofs" by A. Razborov and S. Rudich, September 11 1999. The reference (the one that was already there) mentions an article published in 1994. I don't know why this difference.
The link to the article, as given, does not work.
- The original paper was published in 1994. You will have to look for the pdf in the article link. It worked for me. Josh 21:37, 19 March 2006 (UTC)
Added details[edit]
I added some details to the paper. I'm not an expert, so I asked for one with the {{expert}} template. Also, I'm fairly sure, but not positive, that my statements are correct. For example, I stated that, "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." I'm fairly sure this is true (and the whole point of the paper). If someone knows better, please feel free to correct this. Josh 21:37, 19 March 2006 (UTC)
The article is basically fine. Three touch-ups, and one-or-two suggested additions:
(1) After "one-way functions exist," add `with "exponential hardness" as specified in their main theorem,' then finish the sentence with "Razborov and Rudich..." as you have it.
(2) Insert "(quasi-)" before "polynomial" in the sentence beginning "Roughly". OK, maybe this is too stilted for Wikipedia's standards, but it's efficient:
"Roughly speaking, ... be decidable in (quasi-)polynomial time when the 2^n-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..." [rest as you have it]
(3) After defining /useful/, instead of saying (too narrowly) "P/poly in the paper", write:
"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^0. They give strong evidence..." [rest as you have it]
The suggestion addition at the end is:
There is strong current belief that the mechanism of this paper actually blocks lower-bound proofs against the complexity class <a href="http://en.wikipedia.org/wiki/TC0">TC^0</a> of constant-depth, polynomial-sized threshold circuits, which is believed but not proven smaller than P/poly, as discussed in the "Complexity Zoo" entry for TC^0 <a HREF="http://qwiki.caltech.edu/wiki/Complexity_Zoo#tc0">here</a>. 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.
If you use my last sentence and need a cite, my 2002 survey of the Mulmuley-Sohoni proof strategy for NP != P addresses this issue (<a HREF="http://www.cse.buffalo.edu/~regan/papers/pdf/Reg02MSFD.pdf">PDF file</a>. Please excuse my not taking time right now to seek more recent ones, as you're welcome to do. Also relevant is May 10, 2006 discussion in Lance Fortnow's Weblog <a HREF="http://weblog.fortnow.com/2006/05/importance-of-natural-proofs.html">here</a>.
KWRegan 22:38, 7 January 2007 (UTC)
And of course, one should add or replace the reference by the journal version, as it went through much more substantial refereeing than conference papers typically get: A.~Razborov and S.~Rudich. Natural proofs. {\em J. Comp. Sys. Sci.}, 55:24--35, 1997. <A HREF="http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WJ0-45S92RD-28&_coverDate=08%2F31%2F1997&_alid=519352313&_rdoc=1&_fmt=&_orig=search&_qd=1&_cdi=6864&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=dcbdf84e8579e662a0a53d37e9acf42c">ScienceDirect entry</a> for the official journal version.
This paper won the 2007 Gödel Prize, as already noted in Wikipedia's <a HREF="http://en.wikipedia.org/wiki/Godel_prize">Gödel Prize</a> entry. Is there a standard format for referencing such prizes, e.g. including a link to the <a HREF="http://sigact.acm.org/prizes/godel/2007.html">prize citation itself</a>?
Definition of "natural proof"?[edit]
The article describes "natural properties" and "useful properties", but not "natural proofs". AxelBoldt (talk) 09:23, 9 August 2010 (UTC)
Example Proof?[edit]
This article talks more about what you can't do with natural proofs than what you can do. An example of a natural proof would be nice. — Preceding unsigned comment added by 138.57.212.12 (talk) 21:10, 22 September 2013 (UTC)