DAA - Théorème de Cook
Stephen Cook a présenté quatre théorèmes dans son article «La complexité des procédures de démonstration du théorème». Ces théorèmes sont énoncés ci-dessous. Nous comprenons que de nombreux termes inconnus sont utilisés dans ce chapitre, mais nous n'avons aucune possibilité de tout discuter en détail.
Voici les quatre théorèmes de Stephen Cook -
Théorème-1
Si un ensemble S de chaînes est acceptée par une machine de Turing non déterministe dans un temps polynomial, alors S est P-réductible à {tautologies DNF}.
Théorème-2
Les ensembles suivants sont P-réductibles les uns aux autres par paires (et donc chacun a le même degré de difficulté polynomiale): {tautologies}, {DNF tautologies}, D3, {paires de sous-graphes}.
Théorème-3
Pour toute TQ(k) de type Q, $ \ mathbf {\ frac {T_ {Q} (k)} {\ frac {\ sqrt {k}} {(log \: k) ^ 2}}} $ est illimité
Il y a un TQ(k) de type Q tel que $ T_ {Q} (k) \ leqslant 2 ^ {k (log \: k) ^ 2} $
Théorème-4
Si l'ensemble S de chaînes est accepté par une machine non déterministe dans le temps T(n) = 2n, et si TQ(k) est une fonction honnête (c'est-à-dire dénombrable en temps réel) de type Q, alors il y a une constante K, donc S peut être reconnu par une machine déterministe dans le temps TQ(K8n).
Premièrement, il a souligné l'importance de la réductibilité polynomiale du temps. Cela signifie que si nous avons une réduction de temps polynomiale d'un problème à un autre, cela garantit que tout algorithme de temps polynomial du deuxième problème peut être converti en un algorithme de temps polynomial correspondant pour le premier problème.
Deuxièmement, il a concentré son attention sur la classe NP des problèmes de décision qui peuvent être résolus en temps polynomial par un ordinateur non déterministe. La plupart des problèmes insolubles appartiennent à cette classe, NP.
Troisièmement, il a prouvé qu'un problème particulier de NP a la propriété que tout autre problème de NP peut lui être réduit de manière polynomiale. Si le problème de satisfiabilité peut être résolu avec un algorithme de temps polynomial, alors chaque problème de NP peut également être résolu en temps polynomial. Si un problème dans NP est insoluble, alors le problème de satisfiabilité doit être insoluble. Ainsi, le problème de satisfiabilité est le problème le plus difficile dans NP.
Quatrièmement, Cook a suggéré que d'autres problèmes de NP pourraient partager avec le problème de satisfiabilité cette propriété d'être le membre le plus difficile de NP.