Definition:
Let A and B be sets of problems.
The set A is many-to-one polynomial-time reducible iff there exists a recursive function f(x) such that for all x, x is in A iff f(x) is in B and f(x) can be computed in polynomial time.
This can be written as A≤pB
Explanation:
This definition is usually used as part of algorithm complexity analysis, e.g. proving NP-completeness. You can look at it this way: Let's say you know how to check for membership in set B using an algorithm that executes in polynomial time. If A is reducible to B in this manner it implies that you also know how to check for membership in set A and that there is an algorithm for doing that check that also will execute in polynomial time. The useful conclusion is that if computing f(x) is less complex (i.e. computes faster) than deciding membership in B, B is no more complex than A.
See also: