11

Alexander Razborov and Steven Rudich's Natural Proofs result is one of the major barriers against proving circuit lower bounds. The paper is almost 20 years old (it was published in 1994).

Has there been any result that has avoided the natural proofs' barrier? More formally, has there been any result where the concept of natural proofs makes sense and we provably know that there cannot be a natural proof for the result?

Jeffε
  • 23,129
  • 10
  • 96
  • 163
vzn
  • 11,014
  • 2
  • 31
  • 64
  • 4
    Results that use Geometric Complexity Theory avoid naturalization. – Mahdi Cheraghchi May 31 '13 at 17:52
  • 6
    @MCH: While I agree with you philosophically, what you say isn't quite true (yet). 1) There are very few results that follow the "full" GCT program (e.g. the recent lower bound by Burgisser and Ikenmeyer on matrix multiplication). 2) Those results apply to questions where even their Boolean analogues are not known to have a natural proofs barrier (such as matrix mult). 3) There isn't yet a well-established theory of natural proofs in the algebraic setting. OTOH, a proof which really used characterization by symmetries as suggested in GCT would indeed avoid natural proofs by avoiding largeness. – Joshua Grochow May 31 '13 at 18:05
  • 1
    @MCH by the way merely because a proof is in GCT language does not guarantee it is not "natural", but true, GCT was invented after natural proofs. have not seen any paper that clearly proves that any construction in GCT is not natural, certainly interested in that if it exists. – vzn May 31 '13 at 18:43
  • 3
    Of course I didn't mean any result that uses GCT; obviously saying "any result in which X appears avoids Y" is generally meaningless, and on the other hand GCT is more than just Boolean complexity. My point was that results that use Geometric Complexity Theory have the potential of avoiding naturalization. – Mahdi Cheraghchi May 31 '13 at 18:50
  • 3
    @vzn: maybe you'll find a better explanation in this: http://cstheory.stackexchange.com/questions/170/how-does-the-mulmuley-sohoni-geometric-approach-to-producing-lower-bounds-avoid – Mahdi Cheraghchi May 31 '13 at 18:58
  • 3
    I edited the question. Feel free to edit further if what I wrote is not what you want to ask. ps: I am generally reluctant to edit your questions even when I think interesting questions can be extracted from them because 1. you are not a new user, so the style seems intentional, and 2. I think it is your job to think about your question and write your questions in a reasonable way. (You can start by not making general comments about how experts in a field think without good references.) – Kaveh Jun 05 '13 at 21:48
  • 5
    Look, AFAIK, you are not an expert in complexity theory. If you are making claims about complexity theorist and complexity theory, it is your job to provide sources for those claims. And I can assure you, leaving such comment out of your posts will not hurt your questions. ps: I removed my earlier comments about the question to clean up the thread, I would suggest that you also remove the non-technical ones. pps: We have had enough meta discussions about your general behavior, I don't think we need another one. – Kaveh Jun 05 '13 at 22:30
  • update these course notes state that razborovs own proof of exponential monotone circuit lower bound for cliques is not a natural proof due to not fulfilling the largeness property (p2). also p3 states $\Sigma_3 \subsetneq Size(n^k)$ proof is not natural (what proof is that?) – vzn Oct 21 '13 at 18:55
  • 1
    Isn't this question just restating a part of this question? – Barış Aydınlıoğlu Jun 25 '16 at 13:17
  • Possible duplicate of Proofs, Barriers and P vs NP – Joshua Grochow Dec 29 '18 at 04:41

0 Answers0