Self-reduciblity

Un problème est self-réductible si on peut résoudre sa version recherche en utilisant sa version décision comme oracle.

Définition formelle

Un langage $Q \in 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.

Autrement dit : avec un oracle polynomial pour la version décision, on peut résoudre la version recherche en temps polynomial.

Hypothèse

Si $P=NP$, alors tous les problèmes NP self-réductibles ont des algorithmes polynomiaux pour leurs versions recherche et décision.

Importance théorique

La self-réductibilité montre que pour ces problèmes, les versions décision et recherche ont essentiellement la même difficulté :

• Si la décision est facile (dans P), la recherche l’est aussi
• Si la décision est difficile (NP-complet), la recherche l’est aussi

Exemples de problèmes self-réductibles

Clique

algocliquedec(G, k) -> oui/non  // oracle O(1)

k = TailleMax(G)  // dichotomie : O(log n)
pour x ∈ V:
    si algocliquedec(G\{x}, k):
        G = G\{x}
retourner G

SAT

SATdec(C) -> oui/non  // oracle O(1)

v = []
pour i = 1 à n:
    si SATdec(C[xi=0]):
        C = C[xi=0]
        v[i] = 0
    sinon:
        C = C[xi=1]
        v[i] = 1
retourner v

Sac à dos (Knapsack)

sacadosdec(X, w, u, B, k) -> oui/non

// Trouver k max avec dichotomie
k_max = dichotomie()

// Construire solution
pour x ∈ X:
    si sacadosdec(X\{x}, w, u, B, k_max):
        X = X\{x}
retourner X

Partition

partitiondec(S) -> oui/non

s1 = {x0}, s2 = {}
pour i = 2 à n:
    si partitiondec(S\{xi}):
        s1 = s1 ∪ {xi}
    sinon:
        s2 = s2 ∪ {xi}
retourner (s1, s2)

Coloration de graphe

colordec(G, k) -> oui/non

Idée : Déterminer si deux sommets peuvent avoir la même couleur
      en testant si G avec une arête supplémentaire reste k-coloriable

Hamiltonian Path (HAM)

Retirer progressivement les arêtes en vérifiant l’existence d’un chemin.

Sous-graphe

pour x ∈ V2:
    si sous-graphe(G1, G2\{x}):
        G2 = G2\{x}