In the quest to prove P != NP a great number of techniques have been tried, and many of these techniques have attempted to use circuit complexity. The circuit c

In the quest to prove P != NP a great number of techniques have been tried, and many of these techniques have attempted to use circuit complexity. The circuit complexity of a function with n inputs is, roughly, the size of the smallest circuit that computes it. This is a function depending on n, and so we can talk about polynomial size circuits, etc. The important fact is that if we can find a specific problem (a problem in NP) which doesn't have a polynomial size circuit, then P is not NP. Unfortunately many of the elementary techniques that try to show this don't work, and for a long time nobody knew why. Then in the 90's Alexander Razborov and Steven Rudich proved a general theorem that these elementary techniques could never prove P != NP. What Gowers explains in his blog post (and the follow-up) is the Razborov-Rudich theorem, called natural proofs. Roughly, it says that all of the attempted techniques use a "natural" property P of boolean functions. A natural property P asserts one specific function needs large circuits, while all small circuits cannot satisfy the property (and P is efficiently computable, in a sense). The insight is that all of these properties also apply to TOO MANY other functions. Indeed, if P is natural for polynomial size circuits, and it applies to too many functions, then it can be used to violate another well known conjecture in cryptography, a conjecture on the existence of a certain kind of secure pseudorandom number generator. This is the heart of R-R's theorem, and it's quite a beautiful proof. Nowadays there are three known "barriers" to proving P is not NP, and any proposed method for solving the problem first needs to argue that it bypasses all of these barriers. The first is called relativization (having to do with oracles), the second naturalization (this natural proofs barrier), and the third algebrization (which I'm not familiar with). Tim Gower's is actually using this post as a platform to propose a new method for separating P from NP, and so he's studying these barriers to argue why his method bypasses them. For more on his new proposal, see: http://gowers.wordpress.com/2013/10/24/what-i-did-in-my-summer-holidays/ http://gowers.wordpress.com/2013/10/24/what-i-did-in-my-summ...