19
$\begingroup$

Maybe this is an odd question. It has always bugged me that computability problems are written in all caps, and in such an "awkward" way. SAT, 3-SAT, COLORING, 3-COLORING, PARTITION, CLIQUE, VERTEX COVER. Etc. They're not proper titles, just single words which don't mean much on their own.

Is there any reason for this terminology, especially the all caps part? Who started that terminology?

$\endgroup$
2
  • 2
    $\begingroup$ They are often (today) written in small-caps. $\endgroup$
    – Pål GD
    Aug 24, 2023 at 7:37
  • $\begingroup$ @PålGD You're right, I've also started to see that usage! Quite interesting $\endgroup$
    – Rexon112
    Aug 24, 2023 at 16:09

2 Answers 2

26
$\begingroup$

After the Cook-Levin Theorem Richard Karp realized that the complexity of computational problems could be compared. His paper was prepared in a type-writer font, and used underlining and all-caps for emphasis. Printing technology at the time.

Karp, R.M. (1972). Reducibility among Combinatorial Problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds) Complexity of Computer Computations. The IBM Research Symposia Series. Springer, Boston, MA. https://doi.org/10.1007/978-1-4684-2001-2_9

$\endgroup$
14
$\begingroup$

In the area of discrete mathematics, sets are usually typeset in capital letters. The above problem classes are sets of problems, e.g. SAT is the set of all boolean satisfiability problems.

Thus, the notation is probably consistent with what you are used to from set theory.

$\endgroup$

Your Answer

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

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