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 des limites de la capacité de certains types de calcul. NP fait référence à l'ensemble des problèmes qui peuvent être résolus en temps polynomial par une machine de Turing non déterministe.

Definir Tech explique le temps polynomial non déterministe (NP)

Le temps polynomial non déterministe est basé sur l'expression «temps polynomial», qui se réfère à savoir si un algorithme peut 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 oui ou non cette hypothèse était correcte. Les programmes de définition ou de définition de machine basés sur des vérificateurs testeront essentiellement les choix initiaux de la machine de Turing non déterministe pour vérifier les résultats.

Tout cela est une structure de calcul 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 n'en est encore qu'à ses débuts. Recherchez plus de développement sur cette frontière de l'informatique.