Stephen Cook a-t-il vu l'importance de montrer que SAT est NP-Hard avant de le prouver?
Si je comprends bien, pour prouver que le problème est NP difficile, vous devez sélectionner tous les problèmes possibles qui sont dans NP, puis prouver qu'ils se réduisent à en utilisant une fonction calculable en temps polynomial, qui mappe les instances de chaque aux instances de...