Réduction

En théorie de la calculabilité, une réduction est un procédé qui consiste à ramener un problème à un autre, de manière à transférer ce que l’on sait de l’un vers l’autre. L’idée est la suivante: si l’on dispose d’une méthode mécanique pour transformer toute question du premier problème en une question équivalente du second, alors résoudre le second permettrait automatiquement de résoudre le premier. On dit dans ce cas que le premier problème se réduit au second. Ce raisonnement fonctionne dans les deux sens et sert surtout à propager l’indécidabilité: si l’on sait déjà qu’un problème est impossible à décider, et qu’on parvient à le réduire à un nouveau problème, alors ce nouveau problème est lui aussi indécidable, car s’il était résoluble, l’ancien le serait également, ce qui contredirait ce que l’on sait déjà.

Cette technique s’est développée à partir des années 1930 et 1940, dans le sillage des travaux de Turing, à mesure que les logiciens cherchaient à cartographier le monde des problèmes selon leur difficulté. Plutôt que de reprendre à chaque fois une démonstration longue et délicate par l’absurde, la réduction offrait un moyen économique de démontrer l’indécidabilité de nouveaux problèmes en s’appuyant sur des cas déjà établis, à commencer par le problème de l’arrêt. C’est ainsi que de proche en proche une vaste famille de problèmes a pu être classée, chacun reliant sa propre impossibilité à celle d’un problème connu.

L’esprit de la réduction dépasse largement la calculabilité pure et constitue aujourd’hui l’un des outils les plus féconds de l’informatique théorique. On le retrouve au cœur de l’étude de la complexité, où l’on compare la difficulté des problèmes en les réduisant les uns aux autres pour montrer que certains sont au moins aussi ardus que d’autres. Au fond, réduire, c’est reconnaître qu’un problème nouveau n’est qu’un déguisement d’un problème déjà compris, ce qui permet de réutiliser un savoir acquis plutôt que de repartir de zéro. Cette manière de penser, transformer un problème inconnu en un problème familier, est d’ailleurs une stratégie que les informaticiens et les mathématiciens emploient constamment, bien au-delà des seules questions de calculabilité.