Brian Hayes on Complexity

Brian Hayes, a columnist for American Scientist magazine, gives a wonderful blog entry about the complexity and its confusing use of strange, often weird, terminology.

My concern here is not with the difficulty of the concepts—there’s not much we can do about that—but with the notation and terminology. Do locutions like P^#P and NISZK and (NP ∩ coNP)/poly roll trillingly off your tongue? How about EXP, EEXP, NEXP, PEXP and SUBEXP? And while we’re on the subject of EXP and friends, I’ve been wondering how to pronounce NEXPTIME. (I’m kind of hoping the “P” is silent, as in Pterodactyl.)

And it gets even better:

The sad truth is, the naming conventions for furniture at Ikea make for a more consistent language than those of complexity theory.

Read it all, just for fun.