(Apologies for the triviality of this question; nevertheless, it's been bugging me and presumably people here will be able to answer it...)

It seems that it has become popular in recent years to write the names of complexity classes in a sans serif font (see e.g. these two papers). My question is: where does this notation come from? In particular, what is the first occurrence of the use of this notation in the literature?

The paper "Algorithms for Boolean Function Query Properties" by Scott Aaronson (SIAM Journal on Computing 32(5):1140-1157, 2003; the arXiv version dates back to 2001) uses this notation, but is there anything earlier?

  • 9
    $\begingroup$ I saw it first in "Gems of Theoretical Computer Science" from 1998. It's also used in the German version from 1995. $\endgroup$ Oct 12 '12 at 9:07
  • 2
    $\begingroup$ Karp's paper "Reducibility Among Combinatorial Problems" uses a san-serif font for complexity classes. cs.berkeley.edu/~luca/cs172/karp.pdf $\endgroup$
    – rphv
    Oct 16 '12 at 20:40
  • $\begingroup$ Thanks - it's a bit hard to tell, but squinting, the font used in Karp's paper doesn't seem to be sans serif (there seem to be serifs on the P's). In any case, it isn't the same font as used in the papers I mention above. $\endgroup$ Oct 16 '12 at 21:25
  • 1
    $\begingroup$ Judging from the alphabets at luc.devroye.org/fonts-44934.html I think Karp's paper is using IBM Selectric Script, which is more a handwriting font (like comic sans) than a true sans serif. $\endgroup$ May 14 '14 at 5:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.