Classe DAA - P & NP

En informatique, de nombreux problèmes sont résolus où l'objectif est de maximiser ou de minimiser certaines valeurs, tandis que dans d'autres problèmes, nous essayons de trouver s'il y a une solution ou non. Par conséquent, les problèmes peuvent être classés comme suit -

Problème d'optimisation

Les problèmes d'optimisation sont ceux pour lesquels l'objectif est de maximiser ou de minimiser certaines valeurs. Par exemple,

  • Trouver le nombre minimum de couleurs nécessaires pour colorer un graphique donné.

  • Trouver le chemin le plus court entre deux sommets dans un graphe.

Problème de décision

Il existe de nombreux problèmes pour lesquels la réponse est oui ou non. Ces types de problèmes sont connus sous le nom de decision problems. Par exemple,

  • Si un graphique donné peut être coloré par seulement 4 couleurs.

  • Trouver un cycle hamiltonien dans un graphe n'est pas un problème de décision, alors que vérifier qu'un graphe est hamiltonien ou non est un problème de décision.

Qu'est-ce que la langue?

Chaque problème de décision ne peut avoir que deux réponses, oui ou non. Par conséquent, un problème de décision peut appartenir à une langue s'il fournit une réponse «oui» pour une entrée spécifique. Une langue est la totalité des entrées pour lesquelles la réponse est Oui. La plupart des algorithmes discutés dans les chapitres précédents sontpolynomial time algorithms.

Pour la taille d'entrée n, si la complexité temporelle du pire des cas d'un algorithme est O(nk), où k est une constante, l'algorithme est un algorithme de temps polynomial.

Les algorithmes tels que la multiplication de la chaîne matricielle, le chemin le plus court de source unique, le chemin le plus court de toutes les paires, l'arbre couvrant minimum, etc. s'exécutent en temps polynomial. Cependant, il existe de nombreux problèmes, tels que le vendeur itinérant, la coloration optimale des graphiques, les cycles hamiltoniens, la recherche du chemin le plus long dans un graphique et la satisfaction d'une formule booléenne, pour laquelle aucun algorithme de temps polynomial n'est connu. Ces problèmes appartiennent à une classe intéressante de problèmes, appelés lesNP-Complete problèmes, dont le statut est inconnu.

Dans ce contexte, nous pouvons catégoriser les problèmes comme suit -

Classe P

La classe P comprend les problèmes qui peuvent être résolus en temps polynomial, c'est-à-dire que ces problèmes peuvent être résolus en temps O(nk) dans le pire des cas, où k est constante.

Ces problèmes sont appelés tractable, tandis que d'autres sont appelés intractable or superpolynomial.

Formellement, un algorithme est un algorithme de temps polynomial, s'il existe un polynôme p(n) tel que l'algorithme peut résoudre n'importe quelle instance de taille n dans un temps O(p(n)).

Problème nécessitant Ω(n50) le temps de résolution est essentiellement intraitable pour les grands n. L'algorithme de temps polynomial le plus connu s'exécute dans le tempsO(nk) pour une valeur assez faible de k.

L'avantage de considérer la classe des algorithmes en temps polynomial est que tous deterministic single processor model of computation peuvent être simulés l'un sur l'autre avec au plus un polynôme slow-d

Classe NP

La classe NP comprend les problèmes vérifiables en temps polynomial. NP est la classe des problèmes de décision pour lesquels il est facile de vérifier l'exactitude d'une réponse revendiquée, à l'aide d'un peu d'informations supplémentaires. Par conséquent, nous ne demandons pas un moyen de trouver une solution, mais seulement de vérifier qu'une solution alléguée est vraiment correcte.

Tous les problèmes de cette classe peuvent être résolus en temps exponentiel en utilisant une recherche exhaustive.

P contre NP

Tout problème de décision qui peut être résolu par un algorithme de temps polynomial déterministe peut également être résolu par un algorithme non déterministe de temps polynomial.

Tous les problèmes de P peuvent être résolus avec des algorithmes de temps polynomiaux, alors que tous les problèmes de NP - P sont insolubles.

On ne sait pas si P = NP. Cependant, de nombreux problèmes sont connus dans NP avec la propriété que s'ils appartiennent à P, alors on peut prouver que P = NP.

Si P ≠ NP, il y a des problèmes dans NP qui ne sont ni dans P ni dans NP-Complete.

Le problème appartient à la classe Ps'il est facile de trouver une solution au problème. Le problème appartient àNP, s'il est facile de vérifier une solution qui peut avoir été très fastidieuse à trouver.