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.

Définition formelle

Un problème de décision peut être associé à un langage $L\subseteq \{0,1\}^{*}$, où le problème est d'accepter toutes les entrées dans $L$ et rejeter toutes les entrées qui ne sont pas dans $L$. Pour un problème de promesse, il existe deux langages, $L_{\text{YES}}$ et $L_{\text{NO}}$, qui doivent être disjoints, ce qui signifie $L_{\text{YES}}\cap L_{\text{NO}}=\varnothing$, de sorte que toutes les entrées de $L_{\text{YES}}$ doivent être acceptées et toutes les entrées dans $L_{\text{NO}}$ sont à rejeter. L'ensemble $L_{\text{YES}}\cup L_{\text{NO}}$ s'appelle la promesse. Il n'y a aucune exigence si l'entrée n'appartient pas à la promesse. Si la promesse vaut $\{0,1\}^{*}$ (toutes les entrées), alors c'est aussi un problème de décision, et la promesse est dite triviale.

Exemples

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

Pour prendre un exemple où la promesse influence la complexité, considérons le problème "Étant donné un graphe hamiltonien, déterminez si le graphe a un cycle de taille 4". La promesse est NP-difficile à évaluer, mais le problème est facile à résoudre car la vérification des cycles de taille 4 peut être effectuée en temps polynomial.

Avantages

Oded Goldreich (2006) présente les avantages suivants pour les problèmes à promesse :

1. Les problèmes à promesse sont souvent la forme naturelle de problèmes réels.
2. Les problèmes à solution unique (p.ex. UNIQUE-SAT) ne peuvent être exprimés que comme des problèmes à promesse.
3. Les "gap problems" en optimisation ne peuvent être exprimés que comme des problèmes à promesse.
4. Les classes à promesse peuvent avoir des problèmes complets même quand on n'en connaît pas pour la classe de décision correspondante, comme BPP ou SZK.
5. Elles sont nécessaires pour certains résultats de séparation.

Articles connexes

• Problème de calcul
• Problème de décision
• Problème d'optimisation
• Problème de recherche
• Problème de comptage (complexité)
• TFNP

Lien externe

Références

• Oded Goldreich, Theoretical Computer Science: Essays in memory of Shimon Even, vol. 3895, coll. « LNCS », 2006, 254–290 p. (DOI 10.1007/11685654_12), « On Promise Problems (a survey) »
• A. Sahai et S.P. Vadhan « A complete promise problem for statistical zero-knowledge » (1997) (DOI 10.1109/SFCS.1997.646133)
  — « (ibid.) », dans FOCS 1997, p. 448–457
• Even, Selman et Yacobi, « The complexity of promise problems with applications to public-key cryptography », Information and Control, vol. 61, n^o 2,‎ 1984, p. 159–173 (DOI 10.1016/S0019-9958(84)80056-X)