Computer Science Reduction Notation Mnemonic

By Jacob Strieb

Published on April 21, 2020

Reductions are one of the most important concepts in theoretical computer science. If one problem can be effectively recast as an instance of another via a reduction, they are related, and in some cases equivalent. Since much of academic computer science revolves around studying the complexity of computational problems, understanding the ways in which seemingly different problems relate to one another is critical.

When a computational problem X “reduces” to another problem Y, a Turing machine that computes X can be written using one or more calls to a Turing machine that computes Y.¹ The commonly-used notation for this is:

X ≤ Y

In my introductory theoretical computer science course, several flavors of reductions have been introduced. However, I have found it difficult to remember the reduction notation. Specifically, if X reduces to Y, I have trouble remembering that this means computing X can be made to rely on computing Y. The prevalence of this confusing notation in the course materials and academic literature motivated finding a reliable way to remember its meaning.

My tactic has been to imagine a description for each turing machine (M_X and M_Y) side-by-side, with the “≤” symbol overlaid between them, representing the definition for M_Y zooming in on the call to M_Y in M_X. A poorly-rendered example diagram can be seen below.