import time
import numpy as npComplexity-02 — Vérifier ou trouver : P, NP et la réduction
Navigation : << Complexity-01 — Compter des pas | Index de la série | Complexity-03 — Plus de temps, plus de problèmes >>
Public : Découverte. Deuxième notebook de la série
Complexity/. Il prolonge directement le premier et ne suppose rien d’autre.
Ce que ce notebook suppose
- Complexity-01 — Compter des pas : compter les pas d’un algorithme, la taille \(n\) d’une entrée, le pire cas, le test du doublement, et la frontière entre coût polynomial (\(n\), \(n^2\), \(n^3\)…) et coût exponentiel (\(2^n\)) ;
- lire un programme Python simple (boucles, fonctions récursives, listes, dictionnaires).
Ce que vous saurez faire à la fin
- distinguer trouver une solution et vérifier une solution proposée — le certificat ;
- définir les classes P et NP, et dire ce que NP ne veut pas dire ;
- reconnaître le piège du coût pseudo-polynomial ;
- exécuter une réduction de bout en bout : transformer une instance, la résoudre, retraduire la solution, la vérifier ;
- expliquer pourquoi l’exponentielle reste un mur même pour une machine mille fois plus rapide.
Durée estimée : 60 minutes.
1. Le Sudoku : trouver coûte, vérifier ne coûte presque rien
Un Sudoku illustre l’écart mieux qu’un long discours. Trouver la grille complète demande de la recherche : le solveur le plus simple, le backtracking (retour arrière), remplit la première case vide avec le premier chiffre compatible, continue, et revient en arrière dès qu’il est bloqué. Vérifier une grille proposée demande seulement de relire ses 27 unités (9 lignes, 9 colonnes, 9 blocs) et ses indices de départ.
Le solveur ci-dessous est la version minimale de celui de Sudoku-01 — Backtracking ; il compte ses appels récursifs, le vérificateur compte ses lectures de cases. Les quatre grilles viennent des fichiers de puzzles de la série Sudoku (Sudoku_Easy51.txt et Sudoku_hardest.txt).
GRILLES = {
"facile A": "902005403100063025508407060026309001057010290090670530240530600705200304080041950",
"facile B": "000000907000420180000705026100904000050000040000507009920108000034059000507000000",
"difficile A": "85...24..72......9..4.........1.7..23.5...9...4...........8..7..17..........36.4.",
"difficile B": "12..4......5.69.1...9...5.........7.7...52.9..3......2.9.6...5.4..9..8.1..3...9.4",
}
def lire_grille(texte):
return [0 if ch in ".0" else int(ch) for ch in texte]
def compatible(g, k, v):
r, c = divmod(k, 9)
for j in range(9):
if g[r * 9 + j] == v or g[j * 9 + c] == v:
return False
br, bc = 3 * (r // 3), 3 * (c // 3)
for i in range(3):
for j in range(3):
if g[(br + i) * 9 + bc + j] == v:
return False
return True
def trouver_backtracking(grille):
# Remplit la grille en place ; retourne (reussite, nombre d'appels recursifs).
appels = [0]
def essayer():
appels[0] += 1
if 0 not in grille:
return True
k = grille.index(0)
for v in range(1, 10):
if compatible(grille, k, v):
grille[k] = v
if essayer():
return True
grille[k] = 0
return False
return essayer(), appels[0]
def unites():
lignes = [[r * 9 + c for c in range(9)] for r in range(9)]
colonnes = [[r * 9 + c for r in range(9)] for c in range(9)]
blocs = [[(3 * br + i) * 9 + 3 * bc + j for i in range(3) for j in range(3)]
for br in range(3) for bc in range(3)]
return lignes + colonnes + blocs
def verifier_grille(depart, proposee):
# Certificat accepte ssi il respecte les indices de depart et chaque unite contient 1..9.
lectures = 0
for k in range(81):
lectures += 1
if depart[k] and proposee[k] != depart[k]:
return False, lectures
for unite in unites():
vus = set()
for k in unite:
lectures += 1
vus.add(proposee[k])
if vus != set(range(1, 10)):
return False, lectures
return True, lectures
print(f"{'grille':>12} | {'appels (trouver)':>16} | {'lectures (verifier)':>19} | trouver / verifier")
print("-" * 74)
solutions = {}
for nom, texte in GRILLES.items():
depart = lire_grille(texte)
grille = list(depart)
ok, appels = trouver_backtracking(grille)
valide, lectures = verifier_grille(depart, grille)
assert ok and valide, nom
solutions[nom] = grille
rapport = appels / lectures
rapport_txt = f"{rapport:.2f}" if rapport < 10 else f"{rapport:,.0f}"
print(f"{nom:>12} | {appels:>16,} | {lectures:>19} | {rapport_txt:>14}x".replace(",", " "))
# Un certificat faux doit etre refuse : echanger deux cases d'une solution
fausse = list(solutions["facile A"])
k1, k2 = next((a, b) for a in range(81) for b in range(a + 1, 81)
if a // 9 == b // 9 and GRILLES["facile A"][a] == "0" and GRILLES["facile A"][b] == "0")
fausse[k1], fausse[k2] = fausse[k2], fausse[k1]
valide, lectures = verifier_grille(lire_grille(GRILLES["facile A"]), fausse)
print()
print(f"certificat falsifie (deux cases echangees) : accepte = {valide}, refuse apres {lectures} lectures") grille | appels (trouver) | lectures (verifier) | trouver / verifier
--------------------------------------------------------------------------
facile A | 49 | 324 | 0.15x
facile B | 19 023 | 324 | 59x
difficile A | 335 638 | 324 | 1 036x
difficile B | 228 215 | 324 | 704x
certificat falsifie (deux cases echangees) : accepte = False, refuse apres 180 lecturesLecture. Le vérificateur fait au plus 324 lectures (81 pour les indices, 243 pour les 27 unités), quelle que soit la grille, et il refuse la grille falsifiée. Le solveur, lui, fait de quelques dizaines à plusieurs centaines de milliers d’appels selon la grille : le rapport trouver / vérifier de la dernière colonne se compte en centaines, voire en milliers, sur les grilles difficiles.
Sur la grille la plus facile, trouver coûte même moins que vérifier : l’avantage de la vérification n’est pas d’être toujours plus rapide, c’est d’avoir un coût borné, le même pour toutes les grilles, alors que le coût de la recherche dépend de la grille et peut exploser.
Généralisons à une grille \(m^2 \times m^2\) (le Sudoku classique a \(m = 3\)) :
- vérifier coûte \(4 m^4\) lectures au plus, soit 4 lectures par case : un coût polynomial, et même linéaire en nombre de cases ;
- trouver : le backtracking peut, dans le pire cas, essayer jusqu’à \(m^2\) chiffres par case vide, soit un nombre de branches exponentiel en nombre de cases vides. Personne ne connaît d’algorithme polynomial pour le Sudoku généralisé — et l’on sait pourquoi il serait extraordinaire d’en trouver un (c’est l’objet des sections 3 et 4).
Niveau : le coût de vérification est mesuré ci-dessus ; le fait que le Sudoku généralisé soit NP-complet est cité (Yato & Seta, 2003).
2. Subset-sum : le certificat, et le piège du pseudo-polynomial
Le problème subset-sum (somme de sous-ensemble) est le plus simple des problèmes difficiles :
Instance : une liste de poids entiers positifs et une cible \(t\). Question : existe-t-il un sous-ensemble des poids dont la somme vaut exactement \(t\) ?
C’est un problème de décision : la réponse est oui ou non. Quand elle est oui, un certificat la prouve : la liste des indices des poids choisis. Le vérifier coûte une addition par indice.
Pour trouver, deux algorithmes :
- la force brute essaie les \(2^n\) sous-ensembles ;
- la programmation dynamique remplit une table des sommes atteignables \(0, 1, \dots, t\).
def verifier_subset(poids, cible, indices):
# Certificat = liste d'indices distincts ; retourne (accepte, operations).
operations = 0
if len(set(indices)) != len(indices):
return False, operations
somme = 0
for i in indices:
operations += 1
if not 0 <= i < len(poids):
return False, operations
somme += poids[i]
return somme == cible, operations
def subset_brut(poids, cible):
# Force brute : enumere les 2^n sous-ensembles ; retourne (verdict, operations, certificat).
n = len(poids)
ops = 0
for masque in range(2 ** n):
s = 0
for i in range(n):
ops += 1
if masque >> i & 1:
s += poids[i]
if s == cible:
return True, ops, [i for i in range(n) if masque >> i & 1]
return False, ops, None
def subset_dp(poids, cible):
# Programmation dynamique : table booleenne sur les sommes 0..cible ; retourne (verdict, cases).
atteignable = [False] * (cible + 1)
atteignable[0] = True
cases = 0
for p in poids:
for s in range(cible, p - 1, -1):
cases += 1
if atteignable[s - p]:
atteignable[s] = True
return atteignable[cible], cases
rng = np.random.default_rng(42)
print(f"{'n':>3} | {'ops brut':>10} | {'cases dp':>9} | {'ops verif':>9} | verdict")
print("-" * 52)
for n in (8, 11, 14, 17):
poids = rng.integers(1, 60, size=n).tolist()
cible = int(sum(poids) // 2)
vb, ops_b, certificat = subset_brut(poids, cible)
vd, cases_d = subset_dp(poids, cible)
assert vb == vd, "les deux algorithmes doivent convenir"
if vb:
ok, ops_v = verifier_subset(poids, cible, certificat)
assert ok, "le certificat trouve doit etre accepte"
else:
ops_v = "-" # reponse non : pas de certificat a verifier
print(f"{n:>3} | {ops_b:>10} | {cases_d:>9} | {ops_v:>9} | {'oui' if vb else 'non'}") n | ops brut | cases dp | ops verif | verdict
----------------------------------------------------
8 | 2048 | 734 | - | non
11 | 1925 | 1703 | 5 | oui
14 | 2576 | 2474 | 6 | oui
17 | 8636 | 4457 | 8 | ouiLecture. Sur ces quatre instances, les deux algorithmes rendent le même verdict (l’assert le prouve). Quand la réponse est oui, le certificat trouvé est accepté par le vérificateur en une poignée d’opérations — une par poids choisi. Quand elle est non (première ligne), il n’y a pas de certificat, et la force brute a dû tout essayer : \(2048 = 8 \times 2^8\) opérations. Sur les instances oui, elle s’arrête dès qu’un sous-ensemble convient, ce qui peut arriver tôt. Son pire cas est donc une instance sans solution.
print(f"{'n':>3} | {'ops brut (sans solution)':>24} | {'n * 2^n':>10} | facteur pour 2 poids de plus")
print("-" * 68)
precedent = None
for n in range(10, 19, 2):
poids = [2] * n # que des poids pairs...
cible = 2 * n - 1 # ... et une cible impaire : aucune solution
verdict, ops_b, _ = subset_brut(poids, cible)
assert not verdict and ops_b == n * 2 ** n
facteur = "" if precedent is None else f"x{ops_b / precedent:.2f}"
print(f"{n:>3} | {ops_b:>24,} | {n * 2 ** n:>10,} | {facteur}".replace(",", " "))
precedent = ops_b n | ops brut (sans solution) | n * 2^n | facteur pour 2 poids de plus
--------------------------------------------------------------------
10 | 10 240 | 10 240 |
12 | 49 152 | 49 152 | x4.80
14 | 229 376 | 229 376 | x4.67
16 | 1 048 576 | 1 048 576 | x4.57
18 | 4 718 592 | 4 718 592 | x4.50Lecture. Sans solution, la force brute fait exactement \(n \cdot 2^n\) opérations (l’assert le vérifie) : ajouter deux poids multiplie le travail par un peu plus de 4. C’est la signature exponentielle du premier notebook.
La programmation dynamique semble alors résoudre le problème en coût polynomial : environ \(n \times t\) cases. C’est un piège. La taille d’une entrée n’est pas le nombre de poids, c’est le nombre de symboles qu’il faut pour l’écrire — ici, le nombre total de chiffres. Or multiplier tous les poids et la cible par 10 n’ajoute qu’un chiffre par nombre, mais multiplie \(t\) par 10. Mesurons.
rng = np.random.default_rng(7)
base = rng.integers(1, 60, size=14).tolist()
cible_base = int(sum(base) // 2)
print(f"{'facteur':>8} | {'chiffres de l entree':>20} | {'ops brut':>9} | {'cases dp':>12}")
print("-" * 60)
for k in range(5):
f = 10 ** k
poids = [p * f for p in base]
cible = cible_base * f
chiffres = sum(len(str(p)) for p in poids) + len(str(cible))
vb, ops_b, _ = subset_brut(poids, cible)
vd, cases_d = subset_dp(poids, cible)
assert vb == vd
print(f"{f:>8} | {chiffres:>20} | {ops_b:>9} | {cases_d:>12,}".replace(",", " ")) facteur | chiffres de l entree | ops brut | cases dp
------------------------------------------------------------
1 | 29 | 3542 | 2 882
10 | 44 | 3542 | 28 694
100 | 59 | 3542 | 286 814
1000 | 74 | 3542 | 2 868 014
10000 | 89 | 3542 | 28 680 014Lecture. La même instance, écrite avec des nombres dix fois plus grands à chaque ligne :
- la force brute fait exactement le même travail (elle ne regarde que les combinaisons) ;
- la programmation dynamique voit son nombre de cases multiplié par 10 à chaque ligne, alors que l’entrée ne gagne que 15 chiffres (un par nombre).
Autrement dit, la programmation dynamique est polynomiale en la valeur des nombres, mais exponentielle en leur nombre de chiffres : on dit qu’elle est pseudo-polynomiale. Avec des poids de 30 chiffres — banal en cryptographie —, sa table aurait de l’ordre de \(10^{30}\) cases. Subset-sum reste donc un problème pour lequel aucun algorithme polynomial n’est connu.
3. P et NP
Les deux sections précédentes montrent le même motif : vérifier un certificat est facile, trouver une solution semble difficile. La théorie de la complexité donne un nom à chaque côté.
| Classe | Définition | Exemples |
|---|---|---|
| P | les problèmes de décision qu’un algorithme résout en un nombre de pas polynomial en la taille de l’entrée | trier puis chercher, tester si un nombre est premier, plus court chemin |
| NP | les problèmes de décision dont chaque instance oui possède un certificat de taille polynomiale, vérifiable en un nombre de pas polynomial | Sudoku généralisé, subset-sum, coloriage de graphe en 3 couleurs |
Trois remarques essentielles :
- NP ne veut pas dire « non polynomial ». Le N vient de non déterministe : une machine qui pourrait deviner le bon certificat n’aurait plus qu’à le vérifier. NP est la classe du « facile à vérifier », pas celle du « difficile ».
- P est inclus dans NP : si l’on sait trouver la réponse en temps polynomial, on sait la vérifier — il suffit d’ignorer le certificat et de recalculer.
- La question P = NP est ouverte. Personne ne sait s’il existe un problème de NP qui ne soit pas dans P. C’est l’un des sept problèmes du millénaire du Clay Mathematics Institute, posé formellement par Stephen Cook en 1971.
Pour avancer malgré cette ignorance, on compare les problèmes entre eux. C’est l’outil de la section suivante.
4. Une réduction exécutée de bout en bout : subset-sum vers Partition
Le problème Partition :
Instance : une liste d’entiers positifs. Question : peut-on la couper en deux parts de même somme ?
Réduire subset-sum à Partition, c’est écrire une transformation qui change toute instance de subset-sum en une instance de Partition de même réponse. Alors un algorithme pour Partition résout aussi subset-sum : on transforme, on résout, on retraduit la solution.
La transformation classique ajoute deux nombres. Pour des poids de somme \(\Sigma\) et une cible \(0 \le t \le \Sigma\) :
\[\text{poids} \;\longmapsto\; \text{poids} + [\,\Sigma + t,\; 2\Sigma - t\,]\]
La nouvelle liste a pour somme \(4\Sigma\), donc chaque part doit valoir \(2\Sigma\). Les deux nombres ajoutés font ensemble \(3\Sigma > 2\Sigma\) : ils sont forcément dans des parts différentes. La part qui contient \(2\Sigma - t\) doit donc compléter avec des poids d’origine de somme exactement \(t\) — c’est un certificat de subset-sum. Et réciproquement, un sous-ensemble de somme \(t\) donne une partition. Si \(t > \Sigma\), la réponse est non : on renvoie une instance de Partition sans solution, par exemple [1].
Voici les quatre étapes, exécutées sur un exemple.
def reduire_subset_vers_partition(poids, cible):
# Retourne (instance de Partition, indice de l'element 2*Sigma - t ou None).
total = sum(poids)
if not 0 <= cible <= total:
return [1], None # somme impaire : aucune partition
return list(poids) + [total + cible, 2 * total - cible], len(poids) + 1
def resoudre_partition(valeurs):
# Solveur de Partition (programmation dynamique avec memoire des choix).
# Retourne les indices d'une part de somme totale / 2, ou None.
total = sum(valeurs)
if total % 2:
return None
moitie = total // 2
parent = {0: None} # somme atteinte -> (indice ajoute, somme precedente)
for i, v in enumerate(valeurs):
for s in list(parent): # instantane : chaque element sert au plus une fois
if s + v <= moitie and s + v not in parent:
parent[s + v] = (i, s)
if moitie not in parent:
return None
part, s = [], moitie
while s:
i, s = parent[s]
part.append(i)
return sorted(part)
def retraduire(part, n_origine, indice_marqueur, taille_instance):
# Solution de Partition -> certificat de subset-sum.
if part is None or indice_marqueur is None:
return None
if indice_marqueur not in part:
part = [i for i in range(taille_instance) if i not in part] # prendre l'autre part
return [i for i in part if i < n_origine]
poids, cible = [3, 34, 4, 12, 5, 2], 9
print(f"1. instance de subset-sum : poids = {poids}, cible = {cible}")
instance, marqueur = reduire_subset_vers_partition(poids, cible)
print(f"2. instance de Partition : {instance} (somme {sum(instance)}, chaque part doit valoir {sum(instance) // 2})")
part = resoudre_partition(instance)
print(f"3. solution de Partition : part = {[instance[i] for i in part]}, "
f"autre part = {[instance[i] for i in range(len(instance)) if i not in part]}")
certificat = retraduire(part, len(poids), marqueur, len(instance))
print(f"4. certificat retraduit : indices {certificat} -> poids {[poids[i] for i in certificat]}")
accepte, ops = verifier_subset(poids, cible, certificat)
print(f" verification : accepte = {accepte} en {ops} operations")1. instance de subset-sum : poids = [3, 34, 4, 12, 5, 2], cible = 9
2. instance de Partition : [3, 34, 4, 12, 5, 2, 69, 111] (somme 240, chaque part doit valoir 120)
3. solution de Partition : part = [34, 12, 5, 69], autre part = [3, 4, 2, 111]
4. certificat retraduit : indices [0, 2, 5] -> poids [3, 4, 2]
verification : accepte = True en 3 operationsLecture. Les quatre étapes s’enchaînent : l’instance de subset-sum devient une instance de Partition de huit nombres, le solveur de Partition en trouve une coupe équilibrée, la part qui contient \(2\Sigma - t\) donne les poids d’origine qui font exactement la cible, et le vérificateur de subset-sum accepte ce certificat.
Un exemple ne prouve rien. Faisons tourner la chaîne sur des centaines d’instances aléatoires, en comparant chaque fois le verdict obtenu par la réduction au verdict de la force brute directe.
rng = np.random.default_rng(2026)
resultats = {"oui": 0, "non": 0}
for essai in range(400):
n = int(rng.integers(3, 12))
poids = rng.integers(1, 30, size=n).tolist()
cible = int(rng.integers(0, sum(poids) + 10)) # parfois au-dela de la somme : reponse non
instance, marqueur = reduire_subset_vers_partition(poids, cible)
assert len(instance) <= n + 2 # la transformation est de taille lineaire
certificat = retraduire(resoudre_partition(instance), n, marqueur, len(instance))
verdict_reduction = certificat is not None
verdict_direct, _, _ = subset_brut(poids, cible)
assert verdict_reduction == verdict_direct, (poids, cible)
if verdict_reduction:
assert verifier_subset(poids, cible, certificat)[0]
resultats["oui" if verdict_direct else "non"] += 1
print(f"400 instances : {resultats['oui']} reponses oui, {resultats['non']} reponses non")
print("verdict par la reduction == verdict direct sur les 400 instances ;")
print("chaque certificat retraduit a ete accepte par le verificateur de subset-sum.")400 instances : 201 reponses oui, 199 reponses non
verdict par la reduction == verdict direct sur les 400 instances ;
chaque certificat retraduit a ete accepte par le verificateur de subset-sum.Lecture. Sur toutes les instances, oui comme non, la chaîne transformer → résoudre → retraduire donne le même verdict que la force brute, et chaque certificat retraduit est valide. La transformation ajoute deux nombres et la retraduction relit la solution une fois : leur coût est linéaire.
Ce que la réduction établit, c’est une comparaison de difficulté : Partition est au moins aussi difficile que subset-sum. Si quelqu’un trouvait un algorithme polynomial pour Partition, subset-sum serait résolu en temps polynomial aussi (transformation linéaire + solveur polynomial + retraduction linéaire).
Attention au sens, c’est l’erreur la plus fréquente : réduire A vers B montre que B est au moins aussi dur que A. Réduire un problème difficile vers un problème facile ne prouve rien sur le problème facile ; c’est l’inverse qui transporte la difficulté.
En 1971, Cook a montré qu’un problème de NP (la satisfiabilité de formules logiques, SAT) est au moins aussi difficile que tous les problèmes de NP : on dit qu’il est NP-complet. En 1972, Karp a enchaîné des réductions comme celle-ci pour montrer que 21 problèmes courants — subset-sum et Partition parmi eux — sont eux aussi NP-complets. Conséquence : un algorithme polynomial pour un seul d’entre eux donnerait P = NP. Ce paragraphe est cité ; la réduction ci-dessus est exécutée.
5. Pourquoi l’exponentielle est le mur de l’ingénieur
Revenons à la force brute sur subset-sum. Mesurons combien d’opérations par seconde cette machine exécute, puis extrapolons le temps nécessaire, dans le pire cas (\(n \cdot 2^n\) opérations), pour des tailles plus grandes — sur cette machine et sur une machine mille fois plus rapide.
n_mesure = 18
t0 = time.perf_counter()
_, ops_mesure, _ = subset_brut([2] * n_mesure, 2 * n_mesure - 1)
duree = time.perf_counter() - t0
vitesse = ops_mesure / duree
print(f"mesure : {ops_mesure:,} operations en {duree:.2f} s -> {vitesse:,.0f} operations/s".replace(",", " "))
print()
def lisible(secondes):
for unite, s in (("annees", 31_557_600), ("jours", 86_400), ("heures", 3_600), ("min", 60)):
if secondes >= s:
return f"{secondes / s:,.1f} {unite}".replace(",", " ")
return f"{secondes:.3f} s"
print(f"{'n':>4} | {'ops pire cas':>12} | {'cette machine':>26} | {'machine x1000':>26} | verifier un certificat")
print("-" * 108)
for n in (20, 30, 40, 50, 60, 80):
ops = n * 2 ** n
print(f"{n:>4} | {ops:>12.2e} | {lisible(ops / vitesse):>26} | {lisible(ops / vitesse / 1000):>26} | {n} operations")
def plus_grand_n(vitesse_ops, budget_s):
n = 1
while (n + 1) * 2 ** (n + 1) <= vitesse_ops * budget_s:
n += 1
return n
un_jour = 86_400
n1, n1000 = plus_grand_n(vitesse, un_jour), plus_grand_n(1000 * vitesse, un_jour)
print()
print(f"en un jour : n = {n1} sur cette machine, n = {n1000} sur une machine 1000 fois plus rapide "
f"(+{n1000 - n1} poids seulement)")mesure : 4 718 592 operations en 0.56 s -> 8 471 479 operations/s
n | ops pire cas | cette machine | machine x1000 | verifier un certificat
------------------------------------------------------------------------------------------------------------
20 | 2.10e+07 | 2.476 s | 0.002 s | 20 operations
30 | 3.22e+10 | 1.1 heures | 3.802 s | 30 operations
40 | 4.40e+13 | 60.1 jours | 1.4 heures | 40 operations
50 | 5.63e+16 | 210.6 annees | 76.9 jours | 50 operations
60 | 6.92e+19 | 258 754.4 annees | 258.8 annees | 60 operations
80 | 9.67e+25 | 361 764 888 736.3 annees | 361 764 888.7 annees | 80 operations
en un jour : n = 34 sur cette machine, n = 43 sur une machine 1000 fois plus rapide (+9 poids seulement)Lecture. Les chiffres exacts dépendent de la machine (la première ligne affiche la vitesse mesurée), mais leur forme n’en dépend pas. Dès quelques dizaines de poids, la force brute sort de toute durée raisonnable ; une machine mille fois plus rapide ne recule le mur que d’une dizaine de poids (la dernière ligne en donne le nombre exact), car \(2^{10} = 1024\) : dix poids de plus suffisent à absorber un facteur mille. Pendant ce temps, vérifier un certificat coûte toujours \(n\) opérations.
Voilà le « mur de l’ingénieur » : le matériel fait gagner des facteurs constants, l’exponentielle les absorbe tous. Seul un meilleur algorithme le franchit. Pour les problèmes NP-complets, personne n’en connaît — et la section 4 explique pourquoi en trouver un serait un séisme : il les résoudrait tous.
Exercices
Chaque cellule s’exécute sans erreur telle qu’elle est livrée : remplacez les lignes # TODO etudiant par votre solution.
Exercice 1 — Vérifier un certificat de coloriage
Colorier un graphe avec \(k\) couleurs, c’est donner une couleur à chaque sommet de sorte que deux sommets reliés par une arête n’aient jamais la même couleur. Décider si un graphe est coloriable avec 3 couleurs est NP-complet (cité) ; vérifier un coloriage proposé est facile.
- Etape 1 : écrire
verifier_coloriage(aretes, couleurs, k)qui renvoie le couple(accepte, operations): le certificatcouleurs(une couleur entre 0 et \(k-1\) par sommet) est accepté si aucune arête ne relie deux sommets de même couleur. - Etape 2 : l’appliquer au graphe de Petersen (10 sommets, 15 arêtes) avec les deux certificats fournis — l’un est valide, l’autre non.
- Etape 3 : exprimer le nombre d’opérations en fonction du nombre d’arêtes. Est-ce polynomial ?
# Exercice 1 : a completer
PETERSEN = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0), # cycle exterieur
(0, 5), (1, 6), (2, 7), (3, 8), (4, 9), # rayons
(5, 7), (7, 9), (9, 6), (6, 8), (8, 5)] # etoile interieure
CERTIFICAT_A = [0, 1, 0, 1, 2, 1, 0, 2, 2, 1]
CERTIFICAT_B = [0, 1, 0, 1, 2, 1, 0, 2, 2, 0]
def verifier_coloriage(aretes, couleurs, k):
operations = 0
# TODO etudiant : parcourir les aretes, compter les operations, refuser au premier conflit
return None
for nom, certificat in (("A", CERTIFICAT_A), ("B", CERTIFICAT_B)):
resultat = verifier_coloriage(PETERSEN, certificat, 3)
if resultat is None:
print(f"certificat {nom} : exercice a completer (verifier_coloriage renvoie encore None)")
else:
print(f"certificat {nom} : accepte = {resultat[0]} en {resultat[1]} operations")certificat A : exercice a completer (verifier_coloriage renvoie encore None)
certificat B : exercice a completer (verifier_coloriage renvoie encore None)Exercice 2 — La réduction dans l’autre sens
Partition se réduit aussi vers subset-sum, et cette réduction-là est plus simple : une liste se coupe en deux parts égales si et seulement s’il existe un sous-ensemble de somme totale / 2.
- Etape 1 : écrire
reduire_partition_vers_subset(valeurs)qui renvoie un couple(poids, cible)de même réponse. Attention au cas d’une somme impaire. - Etape 2 : vérifier sur les 200 instances aléatoires de la cellule que le verdict de
subset_dpsur l’instance transformée coïncide avec celui deresoudre_partition. - Etape 3 : avec la réduction de la section 4, qu’en déduisez-vous sur la difficulté relative des deux problèmes ?
# Exercice 2 : a completer
def reduire_partition_vers_subset(valeurs):
# TODO etudiant : renvoyer (poids, cible) tel que la reponse soit la meme
return None
if reduire_partition_vers_subset([1, 5, 6]) is None:
print("Exercice a completer : reduire_partition_vers_subset renvoie encore None")
else:
rng = np.random.default_rng(11)
accords = 0
for _ in range(200):
valeurs = rng.integers(1, 25, size=int(rng.integers(2, 10))).tolist()
poids, cible = reduire_partition_vers_subset(valeurs)
accords += subset_dp(poids, cible)[0] == (resoudre_partition(valeurs) is not None)
print(f"verdicts identiques sur {accords} / 200 instances")Exercice a completer : reduire_partition_vers_subset renvoie encore NoneExercice 3 — Trouver avec un oracle qui ne sait que répondre oui ou non
Supposons qu’on dispose d’une fonction existe(poids, cible) qui répond seulement oui ou non, sans donner de certificat. Peut-on quand même trouver un sous-ensemble ? Oui, avec au plus \(n + 1\) questions : on tente de retirer chaque poids à tour de rôle ; si la réponse reste oui sans lui, on s’en passe définitivement, sinon on le garde et on retire sa valeur de la cible.
- Etape 1 : écrire
trouver_avec_oracle(poids, cible, existe)qui renvoie la liste des indices choisis (ouNonesi la réponse est non), en comptant les appels àexiste. - Etape 2 : vérifier le certificat obtenu avec
verifier_subset. - Etape 3 : expliquer pourquoi ce résultat signifie que, pour subset-sum, décider en temps polynomial suffirait pour trouver en temps polynomial.
# Exercice 3 : a completer
appels_oracle = [0]
def existe(poids, cible):
appels_oracle[0] += 1
return subset_dp(poids, cible)[0]
def trouver_avec_oracle(poids, cible, oracle):
# TODO etudiant : au plus len(poids) + 1 appels a oracle
return None
poids, cible = [3, 34, 4, 12, 5, 2], 9
indices = trouver_avec_oracle(poids, cible, existe)
if indices is None:
print("Exercice a completer : trouver_avec_oracle renvoie encore None")
else:
accepte, _ = verifier_subset(poids, cible, indices)
print(f"indices {indices} -> poids {[poids[i] for i in indices]}, certificat accepte = {accepte}, "
f"{appels_oracle[0]} appels a l'oracle")Exercice a completer : trouver_avec_oracle renvoie encore NoneConclusion
| Problème | Vérifier un certificat | Trouver une solution (meilleur algorithme connu) |
|---|---|---|
| Sudoku \(m^2 \times m^2\) | au plus 4 lectures par case (mesuré : 324 pour \(m = 3\)) | exponentiel dans le pire cas (backtracking mesuré jusqu’à des centaines de milliers d’appels) |
| subset-sum | une addition par poids choisi (mesuré) | force brute \(n \cdot 2^n\) (mesuré) ; programmation dynamique pseudo-polynomiale (mesuré) |
| Partition | une addition par élément | aussi dur que subset-sum : réduction exécutée sur 400 instances |
Ce que ce notebook a établi :
- NP est la classe des problèmes dont les solutions se vérifient vite ; P celle des problèmes qui se résolvent vite. P ⊆ NP, et l’égalité est la grande question ouverte.
- Une réduction compare deux problèmes en transformant les instances de l’un en instances de l’autre ; elle se programme, s’exécute et se teste.
- Le coût se mesure en fonction de la taille écrite de l’entrée : la programmation dynamique de subset-sum n’est polynomiale qu’en apparence.
Le notebook suivant explique l’idée de hiérarchie temporelle : donner plus de temps peut permettre de résoudre de nouveaux problèmes, mais il faut le prouver, pas seulement comparer deux programmes. L’approfondissement 03b conserve le théorème de Hartmanis et Stearns (1965).