1

I teach a theory of computation course and each quarter a student asks me about why reductions between problems are called "reductions." I am not fully sure why this is - saying that "problem A reduces to problem B" often involves turning a seemingly "easier" problem (for example, determining whether a string is in a regular language) into a much "harder" problem (for example, the halting problem) - and the terminology is often a great source of confusion to students.

Is there a historical reason why reductions are called reductions? Is this term related to some other term in mathematics?

Thanks!

templatetypedef
  • 10,206
  • 1
    I rather suspect it is called that because most of the time, the problem you “reduce” the given problem to is either easier, or its solution is already known. And the latter is just another variety of “easier”. – Harald Hanche-Olsen Mar 01 '13 at 20:35
  • I don't know, but our sometimes odd use of the term forms the basis for most of the jokes on this page: http://jcdverha.home.xs4all.nl/scijokes/6_2.html – Trevor Wilson Mar 01 '13 at 20:47

0 Answers0