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?

  • $\begingroup$ 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. $\endgroup$ Commented Sep 27, 2013 at 10:30

1 Answer 1


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.

You might be confusing the mathematical meaning of the term function with its meaning in programming languages, which is what you describe.


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.