Identifier des problèmes difficiles exponentielles sans solution polynomiale.
Réduction de problèmes. Soit un problème X difficile. Le problème Y est aussi difficile que X si on peut efficacement réduire X à Y.
SAT
Soit une expression booléenne complexe (proposition vrai ou faux). Question: peut-on la satisfaire? peut-elle être vrai? Ceci est un problème 2^n selon Cooke/1971. Tout problème de décision est un problème de satisfaction pour N variables. Mais certains sont aussi difficiles que SAT. Ce problème est NP-Complet.
