11
$\begingroup$

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?

Improve this question
$\endgroup$
10
  • 4
    $\begingroup$ Results that use Geometric Complexity Theory avoid naturalization. $\endgroup$
    – Mahdi Cheraghchi
    Commented May 31, 2013 at 17:52
  • 6
    $\begingroup$ @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. $\endgroup$
    – Joshua Grochow
    Commented May 31, 2013 at 18:05
  • 3
    $\begingroup$ 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. $\endgroup$
    – Mahdi Cheraghchi
    Commented May 31, 2013 at 18:50
  • 3
    $\begingroup$ @vzn: maybe you'll find a better explanation in this: cstheory.stackexchange.com/questions/170/… $\endgroup$
    – Mahdi Cheraghchi
    Commented May 31, 2013 at 18:58
  • 5
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Commented Jun 5, 2013 at 22:30

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.