a polynomial-time reduction
/ Karp -> KARP /
A reduction is a translator that turns one problem into another, and you already met it as a tool for transferring undecidability. A polynomial-time reduction is the same idea with a stopwatch attached: the translation must run quickly, in polynomial time. It lets you say 'problem A is no harder than problem B' in the resource-conscious world of P and NP, where speed, not mere solvability, is the currency.
Precisely, a polynomial-time many-one reduction from problem A to problem B (written A <=p B) is a function f, computable in polynomial time, such that for every input x: x is a yes-instance of A if and only if f(x) is a yes-instance of B. To decide A on input x you compute f(x) and ask B. The 'if and only if' keeps yes mapping to yes and no to no, with no flips. Because f runs in polynomial time, the output f(x) also has only polynomial size, which matters: if B then turns out to be solvable in polynomial time, the composition (compute f, then solve B) is still polynomial, so A is solvable in polynomial time too.
That composition property is the engine of the whole NP-completeness theory. If A <=p B and B is in P, then A is in P. Read the contrapositive and it becomes a hardness tool: if A is hard and A <=p B, then B is hard. Polynomial-time reductions are also transitive (A <=p B and B <=p C give A <=p C), which is exactly what lets a single hard problem spread its hardness across thousands of others by chains of reductions. The direction is everything: to prove B is NP-hard you reduce a KNOWN-hard A to B, never the reverse.
INDEPENDENT SET reduces to CLIQUE in polynomial time: given a graph G and number k, build the complement graph G-bar (flip every edge to a non-edge and vice versa) in quadratic time. Then G has an independent set of size k if and only if G-bar has a clique of size k. The translation f(G, k) = (G-bar, k) is the whole reduction.
A <=p B: a polynomial-time function maps yes-instances to yes-instances, so B's solver becomes A's solver with only polynomial overhead.
Direction is the classic trap: A <=p B means B is at least as hard as A, not the other way round. Reduce a known-hard problem TO your target to prove the target is hard.