57. Introduction aux Classes de Complexité : P vs. NP

Les classes de complexité catégorisent les problèmes computationnels en fonction des ressources nécessaires pour les résoudre. Ceci est crucial pour comprendre les limites de la computation.

Classe P (Temps Polynomial)

P signifie 'Polynomial time' (temps polynomial). Cette classe comprend tous les problèmes de décision (problèmes avec une réponse oui/non) qui peuvent être résolus par une machine de Turing déterministe (c'est-à-dire un ordinateur standard) en temps polynomial, c'est-à-dire O(N^k) pour une constante k.

• Exemples : Tri, recherche, recherche du MST.

Classe NP (Temps Polynomial Non Déterministe)

NP comprend tous les problèmes de décision dont la solution peut être vérifiée en temps polynomial. Remarque : NP ne signifie PAS 'Non-Polynomial'.

• Si quelqu'un vous présente une solution potentielle à un problème NP, vous pouvez rapidement vérifier si elle est correcte.
• Exemple : Le Problème du Voyageur de Commerce (TSP). Trouver l'itinéraire le plus court est difficile, mais vérifier qu'un itinéraire proposé est plus court que X est facile.

Le Problème P vs. NP (La Question à Un Million de Dollars)

Est-ce que P = NP ? Est-ce que tout problème dont la solution est rapide à vérifier est également rapide à résoudre ? La plupart des informaticiens croient que P ≠ NP, mais cela reste non prouvé. Les problèmes NP-Complete sont les problèmes les « plus difficiles » de NP.