Classes NP Hard et NP-Complete

Un problème est dans la classe NPC s'il est dans NP et est comme hardcomme tout problème dans NP. Un problème estNP-hard si tous les problèmes de NP lui sont réductibles en temps polynomial, même s'il peut ne pas être dans NP lui-même.

Si un algorithme de temps polynomial existe pour l'un de ces problèmes, tous les problèmes de NP seraient résolubles en temps polynomial. Ces problèmes sont appelésNP-complete. Le phénomène d'exhaustivité des NP est important pour des raisons à la fois théoriques et pratiques.

Définition de l'exhaustivité NP

Une langue B est NP-complete s'il remplit deux conditions

  • B est en NP

  • Chaque A dans NP est le temps polynomial réductible à B.

Si une langue satisfait la deuxième propriété, mais pas nécessairement la première, la langue B est connu comme NP-Hard. De manière informelle, un problème de rechercheB est NP-Hard s'il en existe NP-Complete problème A que Turing réduit à B.

Le problème dans NP-Hard ne peut être résolu en temps polynomial, tant que P = NP. Si un problème s'avère être un NPC, il n'est pas nécessaire de perdre du temps à essayer de trouver un algorithme efficace pour cela. Au lieu de cela, nous pouvons nous concentrer sur l'algorithme d'approximation de la conception.

Problèmes NP-Complete

Voici quelques problèmes NP-Complete, pour lesquels aucun algorithme de temps polynomial n'est connu.

  • Déterminer si un graphe a un cycle hamiltonien
  • Déterminer si une formule booléenne est satisfiable, etc.

Problèmes NP-Hard

Les problèmes suivants sont NP-Hard

  • Le problème de la satisfiabilité des circuits
  • Set Cover
  • Couverture Vertex
  • Problème de vendeur itinérant

Dans ce contexte, nous allons maintenant discuter de TSP is NP-Complete

TSP est NP-Complete

Le problème du voyageur de commerce se compose d'un vendeur et d'un ensemble de villes. Le vendeur doit visiter chacune des villes en partant d'une certaine et en revenant dans la même ville. Le défi du problème est que le voyageur de commerce veut minimiser la durée totale du voyage

Preuve

Prouver TSP is NP-Complete, nous devons d'abord prouver que TSP belongs to NP. Dans TSP, nous trouvons un tour et vérifions que le tour contient chaque sommet une fois. Ensuite, le coût total des bords de la tournée est calculé. Enfin, nous vérifions si le coût est minimum. Cela peut être effectué en temps polynomial. DoncTSP belongs to NP.

Deuxièmement, nous devons prouver que TSP is NP-hard. Pour le prouver, une façon est de montrer queHamiltonian cycle ≤p TSP (car nous savons que le problème du cycle hamiltonien est NPcomplete).

Présumer G = (V, E) être une instance du cycle hamiltonien.

Par conséquent, une instance de TSP est construite. Nous créons le graphique completG' = (V, E'), où

$$ E ^ {'} = \ lbrace (i, j) \ colon i, j \ in V \: \: et \: i \ neq j $$

Ainsi, la fonction de coût est définie comme suit -

$$ t (i, j) = \ begin {cases} 0 & if \: (i, j) \: \ in E \\ 1 & sinon \ end {cases} $$

Maintenant, supposons qu'un cycle hamiltonien h existe dans G. Il est clair que le coût de chaque bord enh est 0 dans G' comme chaque bord appartient à E. Par conséquent,h a un coût de 0 dans G'. Ainsi, si grapheG a un cycle hamiltonien, puis graphe G' a une visite de 0 Coût.

Inversement, nous supposons que G' a une tournée h' du coût au plus 0. Le coût des bords dansE' sont 0 et 1par définition. Par conséquent, chaque bord doit avoir un coût de0 comme le coût de h' est 0. Nous concluons donc queh' contient uniquement des arêtes dans E.

Nous avons ainsi prouvé que G a un cycle hamiltonien, si et seulement si G' a une tournée de coût au plus 0. TSP est NP-complet.