Réduction de Cook-Turing

Une réduction de Cook-Turing (notée ${\ll }_{CT}$​) est plus générale qu’une Réduction de Karp. Elle autorise des appels multiples à un oracle.

Définition

Un problème de décision $Q$ est Cook-Turing réductible à $Q^{\prime }$ s’il existe un algorithme polynomial $A$ résolvant $Q$ qui peut appeler un oracle pour $Q\prime$ un nombre polynomial de fois.

Formellement : $Q{\ll }_{CT}{Q}^{\prime }$ si on peut résoudre $Q$ en temps polynomial en utilisant $Q\prime$ comme sous-routine en temps constant.

Différence avec la réduction de Karp

• Réduction de Karp (${\ll }_P$​) : Un seul appel à l’oracle, transforme l’instance
• Réduction de Cook-Turing (${\ll }_{CT}$ ≪CT$​) : Multiples appels à l’oracle possibles

Q≪PQ′  ⟹  Q≪CTQ′Q \ll_P Q’ \implies Q \ll_{CT} Q’Q≪P​Q′⟹Q≪CT​Q′

mais la réciproque est fausse.

Utilisation : Black box programming

Hypothèse : $P=NP$

Avec un oracle polynomial pour un problème de décision NP-complet, on pourrait résoudre efficacement de nombreux problèmes de recherche.

Exemple : Clique

Oracle : algocliquedec(G, k) retourne OUI/NON en O(1)O(1) O(1)

Algorithme de recherche :

k = TailleMax(G)  // trouve k max avec dichotomie
pour x ∈ V:
    si algocliquedec(G \ {x}, k):
        G = G \ {x}
retourner G

Complexité : O(n)O(n) O(n) appels à l’oracle, donc polynomial.

Lien avec la Self-reduciblity

Un problème Q∈Q \in Q∈ NP est self-réductible s’il existe une réduction de Cook-Turing du problème de recherche vers le problème de décision.