En théorie de la complexité, UP () 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 Leslie Valiant.
Lien externe
Notes et références
Catégorie:Classe de complexité