14
$\begingroup$

(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?

Improve this question
$\endgroup$
4
  • 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$
    – Markus Bläser
    Oct 12, 2012 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, 2012 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$
    – Ashley Montanaro
    Oct 16, 2012 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$
    – David Eppstein
    May 14, 2014 at 5:45

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.