patternMajor
Why are computability problems always written in full caps?
Viewed 0 times
whyfullwrittenarealwayscomputabilityproblemscaps
Problem
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?
Is there any reason for this terminology, especially the all caps part? Who started that terminology?
Solution
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
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
Context
StackExchange Computer Science Q#161731, answer score: 26
Revisions (0)
No revisions yet.