Worldlex Wiki En théorie de la complexité algorithmique , un problème de promesse est une généralisation d'un problème de décision où l'on garantit que l'entrée appartient à un sous-ensemble particulier de toutes les entrées possibles. Contrairement aux problèmes de décision, les instances « oui » (les entrées pour lesquelles un algorithme doit renvoyer « oui » ) et les instances « non » ne constituent pas l'ensemble de toutes les entrées. Intuitivement, l'algorithme a la garantie que l'entrée appartient bien à l'ensemble des instances « oui » ou « non » . Il peut exister des entrées qui ne sont ni « oui » ni « non » . Si une telle entrée est fournie à un algorithme pour résoudre un problème de promesse, l'algorithme est autorisé à produire n'importe quelle sortie, et peut même ne pas s'arrêter.
langage , où le problème consiste à accepter toutes les entrées de et à rejeter toutes les entrées n'appartenant pas à . Dans le cas d'un problème de promesse, il existe deux langages, et , qui doivent être disjoints , c'est-à-dire , tels que toutes les entrées de soient acceptées et toutes les entrées de soient rejetées. L'ensemble est appelé la promesse . Aucune contrainte n'est imposée à la sortie si l'entrée n'appartient pas à la promesse. Si la promesse est égale à , il s'agit également d'un problème de décision, et la promesse est dite triviale.Exemples
De nombreux problèmes naturels sont en réalité des problèmes de promesse. Prenons l'exemple suivant : étant donné un graphe acyclique orienté , déterminer s'il possède un chemin de longueur 10. Les instances « oui » sont les graphes acycliques orientés possédant un chemin de longueur 10, tandis que les instances « non » sont les graphes acycliques orientés ne possédant aucun chemin de longueur 10. La promesse est l'ensemble des graphes acycliques orientés. Dans cet exemple, la promesse est facile à vérifier. En particulier, il est très facile de vérifier si un graphe donné est cyclique. Cependant, la propriété promise peut être difficile à évaluer. Prenons par exemple le problème : « étant donné un graphe hamiltonien , déterminer s'il possède un cycle de taille 4 ». La promesse est alors NP-difficile à évaluer, mais le problème de la promesse est facile à résoudre car la vérification des cycles de taille 4 peut être effectuée en temps polynomial .