Une transformation systématique qui associe des instances et des solutions d’un problème ou d’une structure dans un domaine à des instances et solutions dans un autre domaine de manière à préserver ou refléter la solvabilité ou des propriétés essentielles.

Principe

Une réduction fournit une construction R et une interprétation ou reconstruction S telles que résoudre R(x) dans le domaine cible donne, via S, une solution pour x dans le domaine source ; les réductions ordonnent les problèmes selon leur difficulté relative ou leur expressivité.

Démonstration

En théorie de la calculabilité, une réduction many-one f envoie des instances x du langage A vers des instances f(x) du langage B de sorte que x∈A si et seulement si f(x)∈B ; la décidabilité de B implique donc celle de A en composant un décideur de B avec f.

Mauvaise application

Considérer comme réduction n’importe quel mappage entre problèmes sans vérifier la préservation de l’existence ou de la correction des solutions — par exemple, utiliser un codage injectif qui n’autorise pas la reconstruction d’une solution valide dans le domaine source.

Conséquence

Une réduction correcte transfère des résultats connus : la dureté, la décidabilité/indécidabilité ou des bornes de complexité se propagent de la cible vers la source selon les contraintes de la réduction (par ex. les réductions en temps polynomial préservent les implications de temps polynomial).

Inversion

La relation inverse, lorsqu’elle existe, est une réduction dans l’autre sens ; l’absence de réduction réciproque indique une asymétrie de difficulté ou d’expressivité entre domaines.

Limite

Les réductions requièrent une spécification précise des ressources et transformations autorisées (type : many-one, Turing, temps polynomial, parsimonieuse, etc.) ; les mappages qui modifient le critère d’acceptation ou reposent sur des étapes non constructives sont exclus.

Tension sémantique

Réduction vs équivalence : une réduction montre la transformabilité relative mais pas nécessairement une équivalence bilatérale ; on confond souvent réductions et isomorphismes quand la bidirectionnalité n’est pas établie.

Synthèse

La réduction est un pont constructif : un mappage calculable ou constructif plus une traduction de retour valide qui déplace la solvabilité ou des propriétés structurelles d’un domaine à l’autre selon des contraintes de ressources précisées.