3 ms·
Back when I was taking beginning graduate math classes, the thing that both interested me and frustrated me about complexity classes was that, relative to the c
by joe_the_user 14y ago
Back when I was taking beginning graduate math classes, the thing that both interested me and frustrated me about complexity classes was that, relative to the categories populating other branches of math, it seemed like what distinguished complexity class was simply that the complexity theorists wrinkled their brows and decide one or another classes was "interesting".
Obviously that's somewhat true in other parts of math but other parts of math had a long line of proved theorems along side their feeling that a given structure is interesting. Simple groups can be used to describe all groups in a variety of way. It also have to do with how general a field is. A book on linear differential equations will include many solution whereas a book on non-linear differential equations will mostly existence theorems.
Complexity theory has the problem that proving interesting things about the various classes is very, very hard because computation is a very general activity (proving stuff is itself a form of computation so it get self-referential, etc). In the description of complexity class Z, I felt like I usually saw "Z is trivially greater than X if P=NP but whether Z equals Y is an open problem (and will likely stay open till the sun burns out)".
This isn't to say there isn't mathematics there but it just felt like a much larger portion of the math was elaborate constructions or simple disproofs that anything could be claimed. Cook's Theorem, showing that an NP complete domain existed, is the most substantial, the only substantial theory in the field of complexity classes? Just it actually justify formulating and curating a vast complexity "zoo"? I think this has yet to be determined. I'm doubtful but I haven't struggled through the whole zoo and there may be gems I'm not aware of.
- grandalf 14y agoInteresting! Anyone else have any reaction to this or disagreement?
- nhaehnle 14y agoIANACT, 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.