My friend Marty in grad school mysteriously disappeared in 1985 and showed up yesterday looking exactly the same as I remember him. He said he traveled into my time and asked me how we finally proved P different than NP. I didn't give him the answer he seeked but I let him look around at what complexity has done in the past thirty years. He read through the night and agreed to share his thoughts on this blog.
When I left in '85 Yao and Håstad had just showed that Parity require exponential-size circuits and Razborov showed clique does not have poly-size monotone circuits. Looks like showing some NP problem didn't have poly-size circuits was right around corner so I'm a bit disappointed that didn't happen. I would have thought you would have proven NP is not computable in log space (nope), NP not computable by Boolean formulae (nope) or NP not computable by constant depth circuits with threshold gates (nope). All I see are excuses like "natural proofs". You did show lower bounds for constant depth circuits with modm gates for m prime but that happened back just a year after I left. For m composite you need to go all the way to NEXP and even that took another 25 years.
Back in 1984 we had a 3n lower circuit bound for an explicit function and surely you have much better bounds now, at least quadratic. I almost didn't find any improvement until I saw a paper written last week that improves this lower bound to a whopping 3.011n. You can't make this stuff up.
I shouldn't be that hard on you complexity theorists. All that work on interactive proofs, PCPs, approximations and unique games is pretty cool. Some real impressive stuff on pseudorandom generators and error-correcting codes. Who would have thunk that NL = co-NL or that the entire polynomial-time hierarchy reduces to counting? Nice to see you finally proved that Primes in P and undirected graph connectivity in log-space.
Oh no! Biff stole Lance's copy of Arora-Barak and is taking it back in time. This could change computational complexity forever. I'd better go find Doc Brown and make things right.
[Lance's Note: Thanks to Mostafa Ammar for inspiring this post.]