Calculs déterministes et non déterministes
Pour comprendre la classe P et NP, nous devons d'abord connaître le modèle de calcul. Par conséquent, dans ce chapitre, nous discuterons de deux modèles de calcul importants.
Calcul déterministe et classe P
Machine de Turing déterministe
L'un de ces modèles est la machine de Turing à une bande déterministe. Cette machine se compose d'un contrôle d'état fini, d'une tête de lecture-écriture et d'une bande bidirectionnelle à séquence infinie.
Voici le diagramme schématique d'une machine de Turing à une bande déterministe.
Un programme pour une machine de Turing déterministe spécifie les informations suivantes -
- Un ensemble fini de symboles de bande (symboles d'entrée et symbole vide)
- Un ensemble fini d'états
- Une fonction de transition
En analyse algorithmique, si un problème peut être résolu en temps polynomial par une machine de Turing à une bande déterministe, le problème appartient à la classe P.
Calcul non déterministe et classe NP
Machine de Turing non déterministe
Pour résoudre le problème de calcul, un autre modèle est la machine de Turing non déterministe (NDTM). La structure de NDTM est similaire à DTM, mais nous avons ici un module supplémentaire appelé module de devinettes, qui est associé à une tête d'écriture seule.
Voici le diagramme schématique.
Si le problème est résoluble en temps polynomial par une machine de Turing non déterministe, le problème appartient à la classe NP.