The complexity zoo

From bit-player (Brian Hayes): Until NEXPTIME, on the proliferation of complexity classes.

Have you ever tried to explain to your grandmother why NP is named NP? Does she get it when you say that problems labeled NP-complete are the hardest problems in NP, but NP-hard problems might be harder, and not in NP?

Yes, complexity classes are confusing. As Hayes points out, "There are hints of structure in the naming scheme". I'm not sure if that makes it better or worse. My question is: do there exist complexity classes A, B, C, and D such that the pairs of names (A, B) and (C, D) are related in the same way but the actual classes are related in different ways? In other words, does this nomenclatures have the potential for false generalizations? Hayes points out that the chemists have come up with a good systematic nomenclature for chemical compounds, of which there are many more than there are complexity classes. It's even useful if you're not a chemist; I've caught myself on occasion using the chemist's nomenclature for alkanes to describe trees. (I studied chemistry and math in college.) In particular, if I remember correctly the systematic chemical nomenclature doesn't allow false generalizations.

The trivial chemical nomenclature does, though. ("Trivial" in chemistry doesn't have the mathematician's meaning; in chemistry it means the way in which names are assigned in a one-to-one, ad hoc manner to chemical structures.) Perhaps the Right Thing to do is not to try to regularize the current nomenclature for complexity classes, but to come up with a new systematic naming system that could overlay the current one. But that might require knowing more about complexity theory than we currently do.

There's an inclusion diagram for complexity classes at the Complexity Zoo (which also exists in a wikified version here which appears to be more current.)