Réduction (complexité) | EPFL Graph Search

En calculabilité et en théorie de la complexité, une réduction est un algorithme transformant une instance d'un problème algorithmique en une ou plusieurs instances d'un autre problème. S'il existe une telle réduction d'un problème A à un problème B, on dit que le problème A se réduit au problème B. Dans ce cas, le problème B est plus difficile que le problème A, puisque l'on peut résoudre le problème A en appliquant la réduction puis un algorithme pour le problème B. On écrit alors A ≤ B. Il y a deux utilisations des réductions. Montrer qu'un problème est intrinsèquement difficile. Par exemple, on utilise une réduction pour montrer que des problèmes sont indécidables : on montre alors que le problème est tellement algorithmiquement difficile, qu'il n'y a pas d'algorithmique qui le décide. Les réductions polynomiales sont utilisées pour démontrer que des problèmes sont NP-difficiles. Plus généralement, on démontre avec des réductions qu'un problème est parmi les plus difficiles d'une classe de complexité. Montrer qu'un problème est facile à résoudre algorithmiquement. Par exemple, si A ≤ B avec ≤ une réduction en temps polynomial, et que B appartenant à P, alors A est aussi dans P. Considérons deux problèmes : le problème M de la multiplication de deux entiers, et le problème C de l'élévation au carré d'un entier. Le problème C est plus facile que le problème M. En effet, si l'on sait faire une multiplication, on peut élever un nombre au carré en le multipliant par lui-même, donc C ≤ M. La réduction de C dans M est : on transforme un entier à élever au carré en la donnée de deux entiers égaux (x, x) à multiplier. De manière intéressante, on peut aussi démontrer que M se réduit à C (M ≤ C). En effet, grâce à la formule : on voit que l'on peut calculer le produit de a et b, en calculant trois élévations au carré. Ainsi, les deux problèmes sont aussi difficiles l'un que l'autre (ils peuvent être réduits l'un à l'autre). Les définitions qui suivent mettent en jeu des entiers car les instances des problèmes sont codées dans N.