Complexité des problèmes

#title: "Complexité des problèmes" description: "Classes P, NP, NP-complet et réductions polynomiales"Copier le lien

#Complexité des problèmesCopier le lien

Au-delà de l'analyse des algorithmes individuels, la théorie de la complexité classifie les problèmes eux-mêmes selon leur difficulté intrinsèque. Cette classification permet de comprendre les limites fondamentales du calcul.

#Problèmes de décisionCopier le lien

Un problème de décision est un problème dont la réponse est OUI ou NON.

Exemples :

• SAT : Existe-t-il une affectation satisfaisant une formule booléenne ?
• CLIQUE : Le graphe G contient-il une clique de taille k ?
• CIRCUIT-HAM : Le graphe G contient-il un circuit hamiltonien ?

Tout problème d'optimisation peut être transformé en problème de décision (« Existe-t-il une solution de coût ≤ k ? »).

#Classe PCopier le lien

La classe P contient les problèmes de décision résolubles en temps polynomial par une machine de Turing déterministe.

Exemples de problèmes dans P :

• Tri d'un tableau
• Plus court chemin dans un graphe
• Test de primalité (AKS)
• Programmation linéaire

Les problèmes de P sont considérés comme efficacement résolubles.

#Classe NPCopier le lien

La classe NP (Non-deterministic Polynomial) contient les problèmes dont une solution peut être vérifiée en temps polynomial.

Formellement : un problème est dans NP s'il existe un certificat de taille polynomiale et un vérificateur polynomial.

Exemples :

• SAT : le certificat est une affectation, la vérification est en
• CLIQUE : le certificat est un ensemble de k sommets
• FACTORISATION : le certificat sont les facteurs premiers

Propriété fondamentale :

La question « P = NP ? » est l'un des problèmes du millénaire (prix d'un million de dollars).

#Réductions polynomialesCopier le lien

Une réduction polynomiale de A vers B, notée , est une fonction calculable en temps polynomial qui transforme toute instance de A en instance de B préservant la réponse.

Conséquence : Si et , alors .

#NP-complétudeCopier le lien

Un problème est NP-complet si :

2. Pour tout ,

Théorème de Cook-Levin (1971) : SAT est NP-complet.

#Problèmes NP-complets classiquesCopier le lien

| Problème | Description | |----------|-------------| | SAT | Satisfaisabilité de formules booléennes | | 3-SAT | SAT avec clauses de 3 littéraux | | CLIQUE | Sous-graphe complet de taille k | | VERTEX-COVER | Couverture par sommets | | SUBSET-SUM | Sous-ensemble de somme s | | TSP | Voyageur de commerce (version décision) | | HAMPATH | Chemin hamiltonien | | GRAPH-COLORING | Coloration de graphe en k couleurs |

#Prouver la NP-complétudeCopier le lien

Pour montrer qu'un problème L est NP-complet :

1. Montrer que (donner un certificat et un vérificateur polynomial)
2. Montrer qu'un problème NP-complet connu se réduit à L

#Classe coNPCopier le lien

La classe coNP contient les complémentaires des problèmes de NP.

Exemple : TAUTOLOGIE (une formule est-elle toujours vraie ?) est dans coNP.

#Classes intractablesCopier le lien

#NP-difficileCopier le lien

Un problème est NP-difficile si tout problème de NP s'y réduit, sans nécessairement être dans NP.

Exemple : Le problème d'arrêt est NP-difficile mais pas dans NP (il est indécidable).

#PSPACE et EXPTIMECopier le lien

D'autres classes capturent des ressources différentes :

#Implications pratiquesCopier le lien

#Face à un problème NP-completCopier le lien

1. Algorithmes exacts exponentiels pour les petites instances
2. Heuristiques sans garantie (recuit simulé, algorithmes génétiques)
3. Approximations avec ratio garanti
4. Parameterized complexity : FPT si le paramètre est petit
5. Cas particuliers : certaines restrictions rendent le problème polynomial

Exemple : 2-SAT est dans P, alors que 3-SAT est NP-complet.

#ExercicesCopier le lien

1. Montrez que VERTEX-COVER se réduit à INDEPENDENT-SET.
2. Prouvez que si SAT ∈ P, alors P = NP.
3. Donnez un algorithme de vérification polynomial pour le problème HAMPATH.