Talk:Natural proof
From Wikipedia, the free encyclopedia
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)
[edit] Added details
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.
