Problème Décorélation des Processus (NP-difficile) par réduction à Independent Set

Exercice 2 - Document incomplet

Le document source ne contient aucune donnée ni question sous la section de l'Exercice 2. Il est impossible d'y répondre avec les informations fournies. Nous passons directement à l'Exercice 3.

Exercice 3 - Problème Décorélation des Processus (DecProc)

Question 1 - Appartenance à la classe NP

Pour démontrer qu'un problème de décision appartient à la classe NP, il faut prouver qu'une solution proposée (un certificat) peut être vérifiée par un algorithme en temps polynomial.

Taille du problème : La taille de l'instance est au minimum n + m (où n est le nombre de processus et m le nombre de ressources). Le certificat : Un certificat pour ce problème est simplement un sous-ensemble de processus, c'est-à-dire un sous-ensemble de l'ensemble {1, ..., n}. Ce certificat peut être codé par un vecteur de n booléens. Sa taille est donc au plus n, ce qui est bien inférieur ou égal à la taille du problème.

L'algorithme de vérification : Il doit s'assurer de deux choses :

1. Aucun des processus actifs du certificat ne partage une ressource (l'intersection de leurs ensembles de ressources doit être vide).
2. Le nombre de processus activés (le cardinal) est bien égal à k.

Le document source proposait un pseudo-code que j'ai traduit ici en Python valide pour que vous puissiez l'exécuter. Il prend en entrée les ressources sous forme de dictionnaire d'ensembles (set en Python) pour permettre des opérations d'intersection et d'union rapides.

def verification_certificat(n, P, k, certif):
    """
    Vérifie si un certificat donné est valide pour le problème DecProc.
    
    n : entier, nombre total de processus
    P : dictionnaire associant l'ID du processus (1 à n) à un set() de ses ressources
    k : entier, nombre de processus que l'on souhaite activer
    certif : set(), contient les identifiants des processus proposés (le certificat)
    """
    R = set() # Ensemble des ressources utilisées
    card = 0  # Compteur pour le nombre de processus actifs
    
    for i in range(1, n + 1):
        if i in certif:
            card += 1
            # Vérifie si le processus i partage une ressource déjà utilisée
            if len(P[i].intersection(R)) > 0:
                return False # Conflit détecté sur au moins une ressource
            else:
                R = R.union(P[i])
                
    return card == k

Complexité : L'algorithme parcourt les n processus avec une boucle simple. À l'intérieur, les opérations dominantes sont l'intersection et l'union d'ensembles. En notant t la taille du problème, Pa(t) le coût de vérification de l'appartenance, Pin(t) le test de l'intersection et Pu(t) le coût de l'union, le coût total de cet algorithme est borné par O(n × (Pa(t) + Pin(t) + Pu(t))²). Quelle que soit l'implémentation exacte de ces structures de données, le coût de ces opérations est polynomial par rapport à t. La vérification s'effectue donc bien en temps polynomial, ce qui prouve que DecProc est dans NP.

(Note de correction : Un certificat est simplement un "essai de solution" à vérifier, il n'a pas besoin d'être la solution optimale ou même correcte au moment où on le génère.)

Question 2 - Preuve de NP-difficulté par réduction

L'objectif est de prouver que DecProc est NP-dur en utilisant le problème de l'ensemble indépendant (Independent Set), que l'on sait déjà être NP-dur.

Le piège classique : Il faut réduire le problème connu (Independent Set) vers le problème inconnu (DecProc). Autrement dit, Independent Set ≤p DecProc. Il faut associer à toute instance I de Independent Set une instance red(I) de DecProc de telle sorte que red(I) renvoie VRAI si et seulement si I renvoie VRAI.

La fonction de réduction : Une instance de Independent Set est définie par un graphe composé de Sommets, d'Arcs (arêtes) et d'un entier k0. On construit l'instance red(I) de DecProc ainsi :

• n (le nombre de processus) = le nombre de Sommets.
• m (le nombre de ressources) = le nombre d'Arcs.
• Pour chaque processus i, l'ensemble Pi des ressources qu'il bloque = l'ensemble des arcs adjacents au sommet i.
• k (le nombre de processus à activer) = k0.

Cette transformation est strictement polynomiale : il suffit de compter les sommets, les arcs, et de lister les arcs adjacents pour chaque sommet.

Preuve d'exactitude (les deux sens) :

1. Si I est VRAI (positive) : Il existe un sous-ensemble de k0 sommets indépendants (qui ne partagent aucun arc). Dans notre traduction red(I), les k processus associés ne partagent donc aucune ressource. Ils forment un sous-ensemble de cardinal k que l'on peut activer simultanément. red(I) est donc VRAI.
2. Si red(I) est VRAI (positive) : Il existe un sous-ensemble de k processus activables simultanément sans partager de ressource. Dans le graphe d'origine I, cela signifie que les k sommets associés ne partagent aucun arc, ce qui correspond exactement à la définition d'un ensemble indépendant. I est donc VRAI.

Question 3 - Cas d'une seule ressource par processus

Si chaque processus n'utilise qu'une seule ressource (au lieu d'une liste Pi de taille variable), la complexité s'effondre. Le problème devient polynomial.

Il peut alors être résolu de manière optimale par un simple algorithme glouton (greedy). Il suffit de parcourir les processus et de les activer si la ressource unique dont ils ont besoin n'est pas déjà prise.

Voici la traduction en code Python fonctionnel du pseudo-code fourni dans le corrigé :

def resolution_gloutonne(n, P, k):
    """
    Résout DecProc en temps polynomial si chaque P[i] contient au plus 1 ressource.
    """
    R = set() # Ensemble des ressources utilisées
    card = 0  # Nombre de processus activés
    
    for i in range(1, n + 1):
        # Si aucune des ressources du processus i n'est dans R
        if len(P[i].intersection(R)) == 0:
            card += 1
            R = R.union(P[i])
            
    return card >= k

Question 4 - Cas d'au plus deux processus par ressource

Si chaque ressource est utilisée par au maximum deux processus, le problème reste NP-dur.

La justification repose sur la réduction effectuée à la Question 2. Dans cette réduction, une ressource représente un arc (une arête) du graphe d'origine. Par définition géométrique, un arc relie exactement deux sommets (donc deux extrémités). Ainsi, l'instance de DecProc que nous avons générée pour prouver la NP-difficulté à la Q2 est déjà une instance où chaque ressource est partagée par au maximum deux processus. Puisque cette sous-classe contient déjà un problème NP-dur, elle est elle-même NP-dure.

Question 5 - Complexité du problème d'optimisation (OptProc)

Dans OptProc, au lieu de demander "Peut-on activer k processus ?" (problème de décision), on demande "Quel est le nombre maximum k de processus que l'on peut activer ?".

Ce problème d'optimisation est NP-dur. La logique est une réduction de Turing simple : si nous disposions d'un algorithme polynomial pour résoudre le problème d'optimisation (c'est-à-dire qui nous donne la valeur maximale possible en temps polynomial), il suffirait de comparer ce résultat maximal avec notre cible k pour répondre instantanément au problème de décision DecProc.

Formellement : DecProc(I(n, m, Pi, k)) = VRAI si et seulement si OptProc(I(n, m, Pi)) ≥ k. Puisque le problème de décision DecProc est NP-dur, son grand frère d'optimisation OptProc l'est obligatoirement aussi.

Méthode

Face à un examen portant sur la complexité algorithmique et les classes P/NP, voici les points fondamentaux à sécuriser :

1. Le sens de la réduction est vital : C'est l'erreur la plus coûteuse aux examens. Pour prouver qu'un problème B est NP-dur, vous devez prendre un problème A que l'on sait déjà NP-dur (comme Independent Set, SAT, Clique, etc.) et montrer comment transformer toute instance de A en une instance de B. (A ≤p B). Ne réduisez jamais le problème de l'examen vers un problème connu, cela ne prouve rien sur la difficulté de votre problème.
2. Un certificat n'est pas un algorithme de résolution : Lors de la preuve d'appartenance à NP (Q1), on vous demande de vérifier une solution qu'on vous "donne" magiquement. Ne cherchez pas à construire la solution dans cette étape. Assurez-vous simplement que les opérations de votre vérificateur (boucles, vérification d'ensembles) s'exécutent en temps polynomial.
3. Exploitez les contraintes physiques des graphes : Souvent, les questions de cas particuliers (comme la Q4) se résolvent en regardant votre propre preuve de la Q2. Les arcs d'un graphe ont toujours exactement deux extrémités, ce qui fixe naturellement des limites à 2 dans vos problèmes de ressources ou de conflits.