UP (complexité)
Cet article ne cite pas suffisamment ses sources ().
Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».
En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?
Pour les articles homonymes, voir UP.
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 )
