UP (complexité)
Pour les articles homonymes, voir UP.
Cet article est une ébauche concernant l’informatique théorique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
En théorie de la complexité, UP (en anglais : unambigous non-deterministic polynomial time) est la classe de complexité des problèmes de décision décidés par une machine de Turing non ambigüe (machine de Turing non-déterministe avec au plus une seule exécution acceptante pour une entrée donnée). Cette classe a été défini en 1976 par Valiant[1].
Lien externe
[modifier | modifier le code]Notes et références
[modifier | modifier le code]- Leslie G. Valiant, « Relative complexity of checking and evaluating », Information Processing Letters, vol. 5, no 1, , p. 20–23 (ISSN 0020-0190, DOI 10.1016/0020-0190(76)90097-1, lire en ligne, consulté le )
