Réduction de problème
Un article de Wikipédia, l'encyclopédie libre.
La réduction de problème en théorie de la complexité consiste à réduire un problème connu vers le problème que l'on souhaite classer.
La théorème de Cook a classé en premier le problème SAT comme NP-Complet. Il affirme également qu'il est possible de réduire tous les problèmes NP-Complet au problème SAT, prouvant leur NP-Completude.
Les réductions polynomiales sont des preuves fondamentales en théorie de l'information.
