Problème à promesse

Dans la théorie de la complexité computationnelle, un problème à promesse est une généralisation d'un problème de décision où l'entrée doit appartenir à un sous-ensemble donné de toutes les entrées possibles (la promesse ou précondition), et la sortie reste binaire. Contrairement aux problèmes de décision, les instances positives et négatives n'épuisent pas l'ensemble de toutes les entrées. Si une entrée qui ne satisfait pas la promesse est donnée à un algorithme pour résoudre un problème de promesse, l'algorithme est autorisé à produire n'importe quoi, et peut même ne pas s'arrêter. Un problème de décision peut être associé à un langage , où le problème est d'accepter toutes les entrées dans et rejeter toutes les entrées qui ne sont pas dans . Pour un problème de promesse, il existe deux langages, et , qui doivent être disjoints, ce qui signifie , de sorte que toutes les entrées de doivent être acceptées et toutes les entrées dans sont à rejeter. L'ensemble s'appelle la promesse. Il n'y a aucune exigence si l'entrée n'appartient pas à la promesse. Si la promesse vaut (toutes les entrées), alors c'est aussi un problème de décision, et la promesse est dite triviale. De nombreux problèmes naturels sont en fait des problèmes à promesse. La promesse n'a un impact sur la complexité que si elle est difficile à évaluer. Le problème SAT, par exemple, est souvent décrit comme "Etant donné une formule booléenne, déterminer si elle est satisfaisable". Tel qu'énoncé, c'est un problème à promesse : il n'y a aucune exigence quand l'entrée n'est pas une formule booléenne, comme ")(". C'est donc un abus de langage de dire que SAT est NP-complet, puisque la classe NP ne contient que des problèmes de décision. On peut soit convenir que NP est ici un abus de langage pour PromiseNP, ou changer la définition de SAT pour qu'il demande de rejeter les entrées mal formées, ce qui n'ajoute qu'une vérification en temps polynomial et ne modifie donc pas sa complexité.