CM3

2 types de problèmes:

• Recherche
• Decision (T/F)

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

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.

$MIS{\ll }_{p}MC{\ll }_{p}MVC{\ll }_{p}MIS$

$MIS\ll MC$ $G^{\prime }=\bar{G}$ $k^{\prime }=k$

$MIS\ll MVC$ $G^{\prime }=G$ $k^{\prime }=n-k$

$MC\ll MVC$ $G^{\prime }=\bar{G}$ $k^{\prime }=n-k$