Why do theoreticians in CS use multiple-letter variables?

Question

This is a "dual" question of a popular post on math.se.

Some mathematical objects in computational complexity theory have multiple-letter names. Complexity classes such as $\mathbf{BPP}$ have an established multiple-letter name. So do some computational problems, although the naming convension seems to vary.

I am happy with names such as $\mathbf{BPP}$; however, when I write $\mathbf{PromiseBPP}$ on paper or blackboard over and over, I wish its name were more concise (in fact, some authors prefer to write it as $\mathbf{prBPP}$).
In a popular textbook in complexity, a polynomial that appears in the chapter on algebraic complexity of the book is named as $\mathtt{EXACTLY-ONCE}$, which I do not think is a suitable name to write by hand.

Considering the arguments in the original post on math.se, the pros of shorter names seem to apply more to TCS than those of longer names. After all, what theoreticians do is to work on paper and blackboards, not to write large and complex software with editors that do auto-completion.

Some early literature takes different approach to names. In Cinderella Book, computational problems have concise names such as $L_{\mathrm h}$ (which stands for the Hamiltonian path problem).

Thus the question is: why do theoreticians in CS use multiple-letter variables? Or do we have to give long names to objects we are working on?

Answer 1

I agree with the arguments for shorter variable names on the math.se question, but I disagree that "the pros of shorter names seem to apply more to TCS than those of longer names".

In particular, I don't think the best argument there (which follows) applies here.

I think one reason is that often one does not want to remember what the variable names really represent.

This argument works when the definition is generic, like "n is a number", but not when the definition is quite specific, like "BPP is the class of languages for which there exists a probabilistic Turing machine that runs in polynomial time and outputs 1 with probability greater than 2/3 for all inputs in the language and outputs 1 with probability less than 1/3 for all inputs not in the language".

Sure, if I am dealing with a situation where I DO want to forget the complexity class, then I will use a single letter variable name, like using $\mathcal{C}^L$ to define the relativization of $\mathcal{C}$ with oracle language $L$. But as long as you are working with BPP specifically, I think that it is helpful that the name reminds you that you are working with Polynomial-time Probabilistic (Turing) machines with Bounded error (as opposed to the class of languages that without Bounded error, PP, and the class of languages that is also not based on Probabilistic Turing machines, P).

When we use BPP, we really do want to remember what the variable represents. If this were not the case, then I would not expect everyone to use BPP to denote the above class of languages.

Answer 2

Because we're computer scientists as well as mathematicians, and from the computer science side of the world we've learned the same thing the software engineers have learned about why not to use single-letter names for things other than the most local of variables: longer and more semantically meaningful names are easier to remember and keep straight, easier for others to read and understand, and using them helps avoid certain common errors such as using $k$ to mean three different things in overlapping parts of a paper.

(Actually, I suspect that for the specific case you had in mind, names of complexity classes, this reason is historically inaccurate. But I still believe it's a good reason for using longer names.)

Answer 3

I'm not sure I agree with your premise. I think in most papers, you will find short variable names: some of my personal favorites are $n$, $m$, $i$, $k$, $\epsilon$, and $\alpha$, each quite concise! Now when writing a typeset textbook, one has the luxury to use variable names that make their meaning more apparent to a first-time reader. This is especially true when writing pseudo-code: here, you can borrow from the programming convention of making variable names readable and meaningful, rather than concise.