Une réduction est une traduction : elle transforme toute instance d'un problème en une instance d'un autre, de sorte que les réponses coïncident. Son sens porte tout le raisonnement, et c'est le sens qu'on inverse le plus souvent.
Les deux usages
Prouver une difficulté. Traduire SAT vers un problème B montre que résoudre B permettrait de résoudre SAT, donc que B est au moins aussi difficile.
Résoudre en pratique. Traduire son propre problème vers SAT permet de confier le travail à un solveur, et de profiter de décennies d'ingénierie.
Objectif
Donner le sens de la réduction dans chacun des deux usages, dire si la traduction elle-même doit être peu coûteuse, et nommer la classe pour laquelle SAT est complet.
Répondre aux deux premières questions par l'une des formes proposées entre parenthèses.
Pièges
Les deux usages vont en sens opposés, et c'est ce qui les rend faciles à confondre. Prouver que B est difficile part de SAT. Résoudre son problème avec un solveur arrive à SAT.