UP (complexité)
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
Notes et références
- 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 )
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.