a polynomial-time (Karp) reduction
/ Karp = karp /
Suppose you already know how to solve problem B, and you face a new problem A. A reduction is a way to solve A by quietly translating each of its instances into an instance of B, asking your B-solver, and reporting back its answer unchanged. If the translation is fast, then 'A is no harder than B' — any good algorithm for B gives you one for A for free. It is the same move as 'I can compute areas of triangles, so to find the area of any polygon I cut it into triangles': reuse a solved problem to crack an unsolved one.
Precisely, a polynomial-time (Karp) reduction from decision problem A to decision problem B is a function f, computable in polynomial time, that maps every instance x of A to an instance f(x) of B such that x is a YES-instance of A if and only if f(x) is a YES-instance of B. We write A <=p B. The two demands are: f runs in polynomial time, and it PRESERVES the answer exactly (yes maps to yes, no maps to no). Notice f calls the B-solver only ONCE and just hands back its verdict — that is what 'many-one' means, distinguishing it from more permissive Turing reductions that may call B many times. The point of the polynomial budget is that it cannot itself smuggle in hard work: if B is in P and A <=p B, then A is in P too, because translate-then-solve is polynomial plus polynomial.
Reductions are the load-bearing tool of this whole subject because of what they PRESERVE and TRANSFER. Membership in P flows forward (B easy implies A easy); hardness flows backward (A hard implies B hard). And <=p is transitive — if A <=p B and B <=p C then A <=p C — which lets a single hard problem (SAT) seed a whole zoo of hard problems by chains of reductions. One honest caution about DIRECTION, the most common mistake: 'A reduces to B' means B is at least as hard as A, NOT that A is hard or B is easy. To prove a new problem X is NP-hard you reduce a KNOWN-hard problem TO X (known <=p X), never the other way around.
Reduce independent set to clique. Given (G, k), build the complement graph G' (same vertices; edge in G' exactly where G has none). Then G has an independent set of size k iff G' has a clique of size k, because non-edges become edges. Building G' is O(n^2) — polynomial — and the answer is preserved, so independent-set <=p clique.
f maps instances answer-preservingly in poly time: yes-to-yes, no-to-no, B solved once.
Mind the direction. A <=p B means B is at least as hard as A. To show X is NP-hard, reduce a known-hard problem INTO X, not X into something. And the map must be answer-preserving in BOTH directions of the 'if and only if' — a one-way implication is not a valid Karp reduction.