Eine polynomielle Reduktion transformiert Instanzen eines Problems in polynomieller Zeit in Instanzen eines anderen Problems, wobei die Antwort erhalten bleibt.
Sie zeigt: Wenn das Zielproblem effizient lösbar ist, dann auch das Ausgangsproblem.