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].

Pour les articles homonymes, voir UP.

Lien externe

(en) La classe UP sur le Complexity Zoo

Notes et références

Leslie G. Valiant, « Relative complexity of checking and evaluating », Information Processing Letters, vol. 5, n^o 1,‎ 1^er mai 1976, p. 20–23 (ISSN 0020-0190, DOI 10.1016/0020-0190(76)90097-1, lire en ligne, consulté le 14 juillet 2019)

Portail de l'informatique théorique

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.