3 ms·
IANACT, but complexity theory has advanced a lot since the proof that SAT is NP-complete. There is a lot of hard work on lower bounds on circuits, for example.
by nhaehnle 14y ago
IANACT, but complexity theory has advanced a lot since the proof that SAT is NP-complete. There is a lot of hard work on lower bounds on circuits, for example. Similarly the progress on understanding SDPs and the Unique Games Conjecture. I'm sure there is a lot more.
The fact that there is this whole "complexity zoo" is probably just a symptom of the fact that the field is still very young. As you say, the big problems are very hard, and so people try all sorts of approaches. Many of those approaches lead to the definition of new complexity classes. Once truly big questions start to be resolved, there will most likely be some kind of shakedown process, where the truly important complexity classes are identified, while the others will eventually be nothing but footnotes in the history of the field.
- joe_the_user 14y agoI once chased down the paper where that Russian showed lower bounds on circuits couldn't be used to prove P!=NP. The frustrating thing about the paper was that it lots of references to "what a mathematicians thinks of a proof as" or something like that. IE, it wasn't a formal proof of a general result, didn't claim to be such, but was still taken as a definite word that circuit lower bounds was a dead end for that problem. I'd chase down the real reference if I had time. I'm still not sure exactly how oracle foreclose diagonalization - that seems to also be something complexity theorists take by demonstration rather than formally prove. Anyway, best of luck to them... Edit: Also, it occurs to me that a lot of the core math curriculum, even at the starting graduate level, has been somewhat "sanitized". All the results have been digested to the point of seeming logical from the start. The "edge" of any field probably would look messier than that.