Natural Proofs, Journal of Computing and Systems Sciences, Vol 55, No 1, 1997, pages 24-35. Goto either of their websites for the paper.This is an excellent paper about limits on proof techniques in circuits. Its been blogged about and been described in a wikipedia entry. Very recently Sivakumar wrote a very nice short description of the concept. Has it changed how we do research? The closest analog is the Baker-Gill-Solovay results on Oracles. The contrast:
- Baker-Gill-Solovay showed that techniques that relativize do not suffice to resolve P vs NP. All proofs in recursion theory relativize. Hence we will need more than recursion theory techniques. (Some people disagree with this intepretation. If you are one of them, leave an intelligent comment.) Impact: (1) people got papers for constructing oracles to show that recursion theoretic techniques would not suffice to resolve certain problems, even problems nobody cared about. (2) people began looking more at combinatorial techniques such as circuits since those techniques tend to not relativize. One can argue if this is really true both mathematically and historically. It is possible that the move away from recursion theory to combinatorics was going to happen anyway, or already began. History is messy and hard to put into boxes.
- Razborov and Rudich showed that all lower bounds for circuits (except monotone circuits, for which the terms don't really make sense) ``naturalize'' and that such techniques won't suffice to solve several problems in circuits, including P vs NP, under some reasonable assumptions. There has not been a rush to show certain results naturalize. There has not been a mass movement away from circuits towards something else. But there may be at some later time, and in any case the paper is crucial for telling us what we've been doing and what its limitations are.
- Both results seemed to hint at independence results. Neither one has lead to any such results. Rudich told me once that they were 6 months away from an independence result. 10 years later he told me they are still 6 months away UPDATE IN 2014: STEVE RUDICH TELLS ME THAT HE NEVER SAID THIS. I BELIEVE HIM.
- ``relativize'' was a natural notion that people already knew about at the time of the BGS paper. ``naturalize'' is a less natural notion that Razborov-Rudich discovered or invented for their paper. However it was a very important notion since it captured what many proofs had in common.