<p>Alexander Razborov and Steven Rudich's <a href="http://en.wikipedia.org/wiki/Natural_proof">Natural Proofs</a> result is one of the major barriers against proving circuit lower bounds. The paper is almost 20 years old (it was published in 1994). </p>

<p>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?</p>

CC BY-SA 3.0
2013-10-21T18:55:15.390Z
update these [course notes](http://people.csail.mit.edu/dmoshkov/courses/adv-comp/scribe6.pdf) 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
CC BY-SA 3.0
2013-05-31T17:52:46.163Z
Results that use Geometric Complexity Theory avoid naturalization.
Mahdi Cheraghchi
CC BY-SA 3.0
2013-05-31T18:05:42.880Z
@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
CC BY-SA 3.0
2013-05-31T18:43:29.487Z
@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
CC BY-SA 3.0
2013-05-31T18:50:16.657Z
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
CC BY-SA 3.0
2013-05-31T18:58:47.360Z
@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
CC BY-SA 3.0
2013-06-05T21:48:44.607Z
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
CC BY-SA 3.0
2013-06-05T22:30:36.613Z
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](http://meta.cstheory.stackexchange.com/q/2653/) about your general behavior, I don't think we need another one.
Kaveh
CC BY-SA 3.0
2016-06-25T13:17:32.567Z
Isn't this question just restating a part of [this question](http://cstheory.stackexchange.com/questions/1388/proofs-barriers-and-p-vs-np)?
Barış Aydınlıoğlu
CC BY-SA 4.0
2018-12-29T04:41:48.357Z
Possible duplicate of [Proofs, Barriers and P vs NP](https://cstheory.stackexchange.com/questions/1388/proofs-barriers-and-p-vs-np)
Joshua Grochow
<cc.complexity-theory><reference-request><circuit-complexity><barriers><natural-proofs>
Has there been any result which does not have any Natural Proofs?
vzn
# Has there been any result which does not have any Natural Proofs?

(Asked by: username_0 on 2013-05-31)

Alexander Razborov and Steven Rudich's [Natural Proofs](http://en.wikipedia.org/wiki/Natural_proof) 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?

**Tags:** cc.complexity-theory, reference-request, circuit-complexity, barriers, natural-proofs

> **Comments:**
> **username_1**: Results that use Geometric Complexity Theory avoid naturalization.  
> **username_2**: @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.  
> **username_0**: @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.  
> **username_1**: 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.  
> **username_1**: @username_0: 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  
> **username_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.)  
> **username_3**: 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](http://meta.cstheory.stackexchange.com/q/2653/) about your general behavior, I don't think we need another one.  
> **username_0**: update these [course notes](http://people.csail.mit.edu/dmoshkov/courses/adv-comp/scribe6.pdf) 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?)  
> **username_4**: Isn't this question just restating a part of [this question](http://cstheory.stackexchange.com/questions/1388/proofs-barriers-and-p-vs-np)?  
> **username_2**: Possible duplicate of [Proofs, Barriers and P vs NP](https://cstheory.stackexchange.com/questions/1388/proofs-barriers-and-p-vs-np)  

---

## 0 answers

