Table des matières:
- Définition - Que signifie le temps polynomial non déterministe (NP)?
- Techopedia explique le temps polynomial non déterministe (NP)
Définition - Que signifie le temps polynomial non déterministe (NP)?
Le temps polynomial non déterministe (NP) est en fait un marqueur utilisé pour pointer vers un ensemble de problèmes et de limites de la capacité de certains types de calcul. NP se réfère à l'ensemble des problèmes qui peuvent être résolus en temps polynomial par une machine de Turing non déterministe.
Techopedia explique le temps polynomial non déterministe (NP)
Le temps polynomial non déterministe est basé sur l'expression «temps polynomial», qui fait référence à la capacité d'un algorithme à fonctionner dans certaines limites relatives à la vitesse. Le temps polynomial est apparu comme un moyen de parler de la faisabilité du travail et du développement d'algorithmes.
Si un problème est en temps polynomial non déterministe, la machine de Turing non déterministe peut d'abord deviner la solution, puis exécuter un algorithme vérifiable qui confirmera si cette supposition était correcte ou non. Les programmes de définition de machine ou de définition basés sur un vérificateur testeront essentiellement les choix initiaux de la machine de Turing non déterministe pour vérifier les résultats.
Tout cela est une structure informatique hautement théorique. Alors que l'apprentissage automatique a fait des progrès en allant au-delà des systèmes déterministes, l'idée de vérifier les choix non déterministes en est encore à ses balbutiements. Recherchez plus de développement sur cette frontière de l'informatique.
