Théorème de Cook

Où l'on (re)découvre avec nostalgie son premier problème NP-complet…

Développement

• Théorème de Cook
• Théorème de Cook

Recasements

• 913 -- Machines de Turing. Applications.
• 915 -- Classes de complexité : exemples.
• 916 -- Formules du calcul propositionnel : représentation, formes normales, satisfiabilité. Applications.

Références

• Olivier Carton. Langages formels, calculabilité et complexité.