Problème de décision

Un problème de décision est un problème dont la réponse est soit OUI soit NON.

Définition formelle

Un problème de décision $Q$ est défini par :

• Un ensemble d’instances $I(Q)$
• Un langage $L(Q)\subseteq I(Q)$ (instances pour lesquelles la réponse est OUI)

Résoudre $Q$ pour une instance $i$ consiste à déterminer si $i\in L(Q)$.

Relation avec les problèmes de recherche

Soit QQ Q un Problème de recherche.

Transformation : Recherche → Décision

Decision(D, k):
    si Recherche(D) < k:
        retourner vrai
    sinon:
        retourner faux

Propriétés

• Si un problème de recherche est traitable, le problème de décision est traitable
• Si un problème de décision est non traitable, le problème de recherche est non traitable

Exemples

Stable maximum (MIS)

• Recherche : Trouver un stable de taille maximale
• Décision : Existe-t-il un stable de taille $\ge k$ ?

SAT

• Recherche : Trouver une affectation satisfaisant la formule
• Décision : Existe-t-il une affectation satisfaisante ?

Partition

• Recherche : Trouver deux partitions de somme égale
• Décision : Existe-t-il deux partitions de somme égale ?

Importance en théorie de la complexité

Les classes de complexité (Classe P, Classe NP) sont définies sur les problèmes de décision car ils permettent :

• Une définition formelle claire (langage)
• Des réductions plus simples
• Une théorie unifiée

Mais on peut étendre la notion aux problèmes de recherche via la Self-reduciblity.