[FOM] Almost-natural proofs

[Timothy Y. Chow]

I would like to announce a new preprint that I think FOM readers will be 
interested in, but might otherwise miss since it is nominally a 
computational complexity theory paper rather than a logic or foundations 
paper.

 http://alum.mit.edu/www/tchow/almost.pdf

It concerns Razborov and Rudich's famous paper on "natural proofs," in 
which they argue that existing techniques for proving non-relativizing, 
non-monotone, superlinear lower bounds in circuit complexity theory all 
rely on "natural properties" of Boolean functions, which they demonstrate 
cannot be useful for proving polysize circuit lower bounds unless hard 
pseudorandom number generators do not exist.

What I can show is that if the definition of "natural" is weakened 
slightly, then there provably exist "almost natural properties" that yield 
SIZE(n^d) circuit lower bounds on SIZE(n^(d+epsilon)) computable 
functions.  This result is unconditional.  A second result is that, if 
assumes that pseudorandom number generators exist, then there exist 
"almost-natural proofs" that P != NP.  (Of course if pseudorandom number 
generators exist, then P != NP trivially; the significance is that there 
exist proofs of P != NP having a certain special form.)

Though it was not Razborov and Rudich's intention to stifle interest in 
circuit complexity theory, that seems to have been the de facto 
consequence of their paper.  Perhaps the above results will help revive 
interest in what I feel to be a prematurely abandoned line of research.

Tim