une machine deterministe est un cas particulier de machine nondeterministe : pour la démo à partir de la definition d'une machine nondeterministe, suffit de prendre le cas de la fonction de transfert retournant soit l'ensemble vide soit un singleton, et cela donne une machine deterministe.
donc si tu es en temp polynomial sur une machine nondeterministe, rien n'indique que c'est en temps polynomiale sur une machine à état deterministe.
par contre, un algo O(1) sur une machine déterministre donnera sans doute un algo O(1) sur une non déterministe est une perle. la raison est simple si un algo est en O(1) sur une machine deterministe alors ce meme algo est en O(1) sur une nondeterministe, c'est une conséquence du fait que la machine deterministe est un cas particulier des machines non deterministes.
Par contre, un algo en O(1) sur une machine non deterministe, ne sera pas necessairement en O(1) sur une machine deterministe.
Dans le cas des problemes NP-complet, c'est la classe extreme des probleme NP.
Et pour rappel, tout porte à penser que NP != P et non P = NP .
[^] # Re: d'un autre coté ...
Posté par Mouns . En réponse au journal La NSA et la vie privée. Évalué à 0.
donc si tu es en temp polynomial sur une machine nondeterministe, rien n'indique que c'est en temps polynomiale sur une machine à état deterministe.
par contre, un algo O(1) sur une machine déterministre donnera sans doute un algo O(1) sur une non déterministe est une perle. la raison est simple si un algo est en O(1) sur une machine deterministe alors ce meme algo est en O(1) sur une nondeterministe, c'est une conséquence du fait que la machine deterministe est un cas particulier des machines non deterministes.
Par contre, un algo en O(1) sur une machine non deterministe, ne sera pas necessairement en O(1) sur une machine deterministe.
Dans le cas des problemes NP-complet, c'est la classe extreme des probleme NP.
Et pour rappel, tout porte à penser que NP != P et non P = NP .