# NP-COMPLETE:Why say "reduction algorithm computes reduction function"?

In Chap 34.3 NP-completeness and reducibility of the book, Introduction to Algorithm(3rd Edition), the author states(the original text):

We call the function f the reduction function, and a polynomial-time algorithm F that computes f is a reduction algorithm.

In my mind, function should be a machine dependent implementation(a set of instructions) of the algorithm. Why does he say algorithm computes function?

• Because a function is the abstract mathematical thingy that an algorithm computes. Do not confuse this with "functions" in programming languages, which are more like algorithms than mathematical functions. Sep 27, 2013 at 10:30

A function is a mapping from elements in the domain to elements in the range. Here is an example of a function: $f(n) = n!$. If you want a machine to compute $f(n)$ given $n$, you need an algorithm, for example: given $n$, multiply together all the numbers from $1$ to $n$. There can be other algorithms for computing $f$. The function exists without reference to a machine. In fact, some functions (such as the halting function) cannot be computed by any algorithm.