Réduction polynomiale

Une réduction polynomiale est une transformation d’un problème vers un autre qui préserve les réponses et s’exécute en temps polynomial.

Types de réductions

Réduction de Karp (${\ll }_P$​)

Transformation d’instance en temps polynomial :

$$f:I(Q_1)\to I(Q_2)\text{ telle que }i\in L(Q_1)⟺f(i)\in L(Q_2)$$

Réduction de Cook-Turing (${\ll }_{CT}$​)

Autorise des appels multiples à un oracle pour résoudre le problème.

Propriétés fondamentales

Transitivité

$$Q_1{\ll }_P{Q}_2\text{ et }{Q}_2{\ll }_P{Q}_3⟹Q_1{\ll }_P{Q}_3$$

Préservation de la difficulté

Si $Q_1{\ll }_P{Q}_2$​ alors :

• $Q_2\in P⟹Q_1\in P$
• $Q_1\notin P⟹Q_2\notin P$

Application : NP-complétude

Pour prouver qu’un problème $Q$ est NP-difficile, il suffit de :

1. Choisir un problème $Q^{\prime }$ déjà connu comme NP-complet
2. Construire une réduction $Q^{\prime }{\ll }_{P}Q$

Théorème

Si $Q$ est NP-complet et $Q{\ll }_P{Q}^{\prime }$ avec $Q^{\prime }\in$ NP, alors $Q^{\prime }$ est NP-complet.

Preuve : Soit $Q^{\prime \prime }\in$ NP quelconque.

• $Q^{\prime \prime }$ NP-complet $⟹Q^{\prime \prime }{\ll }_{P}Q$
• $Q{\ll }_P{Q}^{\prime }$ (par hypothèse)
• Par transitivité : $Q^{\prime \prime }{\ll }_P{Q}^{\prime }$

Donc $Q^{\prime }$ est NP-difficile, et comme $Q^{\prime }\in$ NP, $Q^{\prime }$ est NP-complet.

Exemples de chaînes de réductions

$$\text{SAT}{\ll }_P\text{3-SAT}{\ll }_P\text{MIS}{\ll }_P\text{VC}$$ $$\text{MIS}{\ll }_P\text{Clique}\text{ via }G\to \overline{G}$$ $$\text{Partition}{\ll }_P\text{Sous-somme}{\ll }_P\text{Sac aˋ dos}$$