Un problème de recherche demande de trouver une solution optimale ou satisfaisante parmi un ensemble de solutions possibles.
Définition
Contrairement à un Problème de décision qui répond OUI/NON, un problème de recherche doit construire ou exhiber une solution.
Exemples
Stable maximum (MIS)
- Décision : Existe-t-il un stable de taille ?
- Recherche : Trouver un stable de taille maximale
SAT
- Décision : La formule est-elle satisfiable ?
- Recherche : Trouver une affectation satisfaisante
Coloration de graphe
- Décision : Le graphe est-il -coloriable ?
- Recherche : Trouver une coloration valide avec le minimum de couleurs
Relation avec les Problème de décision
Transformation : Recherche → Décision
Decision(D, k):
si Recherche(D) < k:
retourner vrai
sinon:
retourner faux
Propriété de réduction
- Si le problème de recherche est traitable, le problème de décision est traitable
- Si le problème de décision est non traitable, le problème de recherche est non traitable
Self-réductibilité
Certains problèmes permettent de résoudre la version recherche à partir de la version décision via un oracle : voir Self-reduciblity.