La réduction est une transformation d'un problème Π à un problème Π' qui permet de préserver une certaine propriété. Par exemple, la réduction de Karp permet de transporter la résolution polynomiale des problèmes de décision : si Π se réduit à Π' par une réduction de Karp et qu'il existe un algorithme polynomial A permettant de décider Π', alors par le biais de cette réduction, on sait construire à partir de A un algorithme polynomial permettant de décider Π. Pour les problèmes d'optimisation, on cherchera à préserver un degré d'approximation : la résolution exacte, l'approximation à rapport constant, les schémas d'approxmation etc..