Complexity Zoo Pronunciation Guide

From Complexity Zoo
Revision as of 03:10, 18 November 2012 by Admin (talk | contribs) (1 revision: Complexity zoo import.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

This page is a pronunciation guide for the Complexity Zoo which was originally created at http://www.complexityzoo.com/ by Scott Aaronson.


Unfortunately, there are no accepted conventions for pronouncing the names of rarer complexity classes. Usually the safest bet is just to spell out a whole acronym; even when vowels are present, this is easier than wrapping one's tongue around (say) PODN or NISZK. The major exceptions are words and word prefixes, which are pronounced as such: for example, co, mod, log, lin, few, poly, exp, gap, time, space, amp, av, sel, sat. Also, the "TAS" in PTAS, FPTAS, and EPTAS is generally pronounced "tahz."

As for symbols, the "⊕" of ⊕L is pronounced "parity"; while the "#" of #P is pronounced "sharp" (some textbooks also list "pound" or "number" as acceptable, but I've never heard the latter two used in real life (update: Leslie Ann Goldberg tells me that in Britain, they say both "number-P" and "hash-P")). The "/" of P/poly is pronounced "slash." The act of subscripting is left unvocalized, so that ModkP is "mod-k-p" rather than "mod-sub-k-p." Superscripting, on the other hand, is vocalized: PNP is "P to the NP" (but not "P to the NP power" - it's an oracle, for Godsakes).

Finally, Lance Fortnow has informed me that C=P and its cousin C=L are pronounced "C equals P" and "C equals L" respectively. This could lead to confusion in sentences such as coNQP equals C equals P."