réduction

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.