[FOM] Almost-natural proofs
Timothy Y. Chow
tchow at alum.mit.edu
Fri May 9 14:57:14 EDT 2008
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
More information about the FOM
mailing list