3
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 11
    $\begingroup$ You seem to be conflating local variables and global names, but I think these are very different. Maths and CS both have "long" names (e.g. "topology", , "Hamiltonian path problem", "Hausdorff space", "Borel sigma-algebra", "BPP", "solvable groups"). But I am not sure I agree that CS tends to use long variables (can you provide an example?). I think it's common in CS to say "Let $G$ be a graph", "Let $M$ be a polytime algorithm", "Let $X$ be the expected number of samples". So I think single-letter variables are common. $\endgroup$ – usul Oct 12 '13 at 15:32
  • 8
    $\begingroup$ I agree with usul. Mathematicians also use long names for global variables, e.g. standard functions $\sin x$, $\cos x$, $\log x$, $\dim V$, $\mathrm{rank}\, M$, $\mathrm{Var}[X]$, $\mathrm{ord}(a)$ etc or standard categories $\mathrm{Set}$, $\mathrm{Top}$, $\mathrm{Met}$, $\mathrm{Grp}$ etc. $\endgroup$ – Yury Oct 12 '13 at 15:48
  • $\begingroup$ I say "variables", because the original question on math.se is formulated as such. They are not necessarily meant to be local. By "names", I mean symbols assigned to mathematical entities such as sets, numbers and functions. I feel no problem with long technical terms such as "Hamiltonian path problem", or moderately long global names such as $\mathbf{BPP}$. My question is about verbose global names such as $\mathbf{PromiseBPP}$ and long local names such as $\mathtt{EXACTLY-ONCE}$, which I think is local because it is referred in the text only once. $\endgroup$ – Pteromys Oct 13 '13 at 2:56
  • $\begingroup$ the original question and most of its answers actually talk about variables though, things that vary. and your examples are names of fixed objects. as to this Exactly-Once polynomial, you answered your own question: when something is named once (the irony!) in the text, why not name it descriptively, it's not like you'd have to write it over and over as a part of complicated computations. $\endgroup$ – Sasho Nikolov Oct 13 '13 at 19:43
  • $\begingroup$ My thought about $\mathtt{EXACTLY-ONCE}$ was that if it is so unimportant an object that it is referred only once, it doesn't have to have a descriptive name. As you've said, it is not a cumbersome name, though. $\endgroup$ – Pteromys Oct 14 '13 at 11:02
5
$\begingroup$

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.

Improve this answer
$\endgroup$
7
$\begingroup$

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.)

Improve this answer
$\endgroup$
2
  • 7
    $\begingroup$ "We learned it from programming" is just the answer that I was going to give! But I further agree that complexity classes are a different case than "ordinary" variable names. Indeed I'd add that, when facing somewhat analogous tasks as naming complexity classes -- such as naming Lie groups (SU, SO, PSL...) or categories (Int, Set...) -- even the pure mathematicians resort to multiple-letter names as well. $\endgroup$ – Scott Aaronson Oct 13 '13 at 8:28
  • $\begingroup$ My original idea was that while long and descriptive names help software engineers that write large, complex programs, they might not be as useful for theoreticians, whose target is somewhat different from that of engineers. $\endgroup$ – Pteromys Oct 13 '13 at 12:20
3
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ Aaron, I see you like $\epsilon$ but not $\delta$ :) $\endgroup$ – Sasho Nikolov Oct 12 '13 at 13:55
  • 1
    $\begingroup$ $\delta$ sucks! $\endgroup$ – Aaron Roth Oct 12 '13 at 13:59
  • 6
    $\begingroup$ I much prefer $\varepsilon$ to $\epsilon$. $\endgroup$ – Tyson Williams Oct 12 '13 at 14:09
  • 6
    $\begingroup$ By looking at the prevalence of \eps in text abstracts, I conclude that \newcommand{\eps}{\varepsilon} is quite common. $\endgroup$ – András Salamon Oct 12 '13 at 15:32

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.