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.]
What I find disappointing isn't so much the lack of results but the lack of ideas/methods to FIND new results.
ReplyDeleteAll papers on complexity look like arcane ugly tinkerings.
That it is hard to prove results related to NP is not a surprise to me, by the definition of the class: problems with polynomial results so long as you can select them by magic.
ReplyDeleteAs anyone who has ever tried to argue against someone with a supernatural belief can tell you, it is very hard to disprove the existence of magic... How do you even formalize it?
You could have told Marty that his own time travel (assuming reproducibility) just proved a range of new results in complexity theory, including P=NP ;)
ReplyDeleteMarty: So I suppose that the entire community go to STOC or FOCS and most people can understand most of the results. Oh, the Europeans might go to ICALP instead.
ReplyDeleteOh well. Marty might be surprised that there are so many conferences and its much harder for anyone to know all or even half or even 10% of what is known in TCS.
Is this surprising or do most fields grow that much in 30 years? Perhaps most young fields do.
BTTF has a problem that many science fiction movies have (Lance commented on this with regard to the movie Herbie: Fully Loaded, http://blog.computationalcomplexity.org/2015/10/complexity-blast-from-past.html#comment-form)
Time travel is possible! having said that any plot point of BTTF seems trivial.