3 ms·
The two blog posts by Gowers are attempting to provide an exposition of the Razborov--Rudich paper "Natural Proofs" (http://citeseerx.ist.psu.edu/viewdoc/downlo
by cokernel 13y ago
The two blog posts by Gowers are attempting to provide an exposition of the Razborov--Rudich paper "Natural Proofs" (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.41.2663&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.41....).
One way to try to prove that P != NP is to identify some "natural combinatorial property" that problems in P have that problems in NP do not share. The problem (as Gowers explains) is that any such property is either incredibly complicated or actually applies to almost any random problem in NP. Razborov and Rudich state and prove a technical version of this statment, which implies that attempting to use "natural combinatorial properties" to prove P != NP is a non-starter. (Hence the title of Gowers's blog post.)
For another summary, you might look at the relevant article on Wikipedia (http://en.wikipedia.org/wiki/Natural_proof http://en.wikipedia.org/wiki/Natural_proof). But I'd recommend reading Gowers's writing, which is much clearer.