Comment prouver qu'un problème est NP complet?

108

J'ai un problème avec la planification. J'ai besoin de prouver que le problème est NP complet. Quelles peuvent être les méthodes pour prouver qu'il est NP complet?

algorithm Thetna
la source
Lisez "Réductibilité parmi les problèmes combinatoires" par Karp.
Paul Hankin

Réponses:

146

Pour montrer qu'un problème est NP terminé, vous devez:

Montrez que c'est dans NP

En d'autres termes, compte tenu de certaines informations C, vous pouvez créer un algorithme de temps polynomial Vqui vérifiera pour chaque entrée possible Xsi elle Xest dans votre domaine ou non.

Exemple

Prouvez que le problème des couvertures de sommets (c'est-à-dire, pour un graphe G, a- t-il un ensemble de couvertures de sommets de taille ktelle que chaque arête Ga au moins un sommet dans l'ensemble de couvertures ?) Est dans NP:

  • notre entrée Xest un graphique Get un nombre k(cela provient de la définition du problème)

  • Prenons nos informations Ccomme "n'importe quel sous-ensemble possible de sommets dans un graphe Gde taille k"

  • Ensuite, nous pouvons écrire un algorithme Vqui, étant donné G, ket Cretournera si cet ensemble de sommets est une couverture de sommets pour Gou non, en temps polynomial .

Alors pour chaque graphe G, s'il existe un "sous-ensemble possible de sommets Gde taille k" qui est une couverture de sommets, alors il Gy en a NP.

Notez que nous n'avons pas besoin de trouver Cen temps polynomial. Si nous pouvions, le problème serait dans `P.

Notez que l'algorithme Vdevrait fonctionner pour tous G , pour certains C. Pour chaque entrée, il devrait exister des informations qui pourraient nous aider à vérifier si l'entrée est dans le domaine du problème ou non. Autrement dit, il ne devrait pas y avoir d'entrée où l'information n'existe pas.

Prouvez que c'est NP Hard

Cela implique d'obtenir un problème NP-complet connu comme SAT , l'ensemble des expressions booléennes sous la forme:

(A ou B ou C) et (D ou E ou F) et ...

là où l'expression est satisfiable , c'est qu'il existe un paramètre pour ces booléens, ce qui rend l'expression vraie .

Réduisez ensuite le problème NP-complet à votre problème en temps polynomial .

Autrement dit, étant donné une entrée Xpour SAT(ou quel que soit le problème NP-complet que vous utilisez), créez une entrée Ypour votre problème, telle que Xdans SAT si et seulement si Yest dans votre problème. La fonction f : X -> Ydoit s'exécuter en temps polynomial .

Dans l'exemple ci-dessus, l'entrée Yserait le graphique Get la taille de la couverture de vertex k.

Pour une preuve complète , vous devrez prouver les deux:

  • c'est Xdans SAT=> Ydans votre problème

  • et Ydans votre problème => Xin SAT.

La réponse de marcog a un lien avec plusieurs autres problèmes NP-complets que vous pourriez réduire à votre problème.

Note de bas de page: À l'étape 2 ( prouver qu'il est NP-difficile ), la réduction d'un autre problème NP-difficile (pas nécessairement NP-complet) au problème actuel fera l'affaire, puisque les problèmes NP-complet sont un sous-ensemble de problèmes NP-difficiles (qui sont également en NP).

Laila Agaev
la source
7
Je me demande s'il y a des données manquantes ou un raisonnement circulaire derrière cela. Je veux dire comment «prouver» qu'un problème est dans NP sans le référer à un autre problème qui «est déjà dans NP»? C'est comme dire "il est fait de fer parce que sa partie est connue pour être du fer", ce n'est pas une preuve de fer.
Hernán Eche
6
Autant que je me souvienne, il existe un théorème appelé le théorème de Cook-Levin qui déclare que SAT est NP-complet. Cette preuve est un peu plus compliquée que ce que j'ai décrit ci-dessus et je ne pense pas pouvoir l'expliquer avec mes propres mots.
Laila Agaev
4
Pour être plus précis, le théorème de Cook-Levin déclare que SAT est NP-complet: tout problème de NP peut être réduit en temps polynomial par une machine de Turing déterministe au problème de déterminer si une formule booléenne est satisfiable (SAT). Voilà donc la pièce manquante dont vous parliez. Si vous recherchez le théorème sur Wikipedia, il y a une preuve, et vous pouvez référencer le théorème dans votre preuve. Cela dit, réduire SAT à un problème donné est la façon dont on m'a appris à prouver l'exhaustivité de NP.
Laila Agaev
Donc ma question finit par être de savoir si SAT pouvait être résolu en polynôme c'est à dire le problème P = NP .. Merci pour votre réponse.
Hernán Eche
Pourriez-vous s'il vous plaît expliquer pourquoi nous ne pouvons pas réduire un problème NP-difficile au problème que nous voulons, dans la deuxième étape? Doit-il s'agir d'un problème NP-complet?
MLT
23

Vous devez réduire un problème NP-Complete au problème que vous rencontrez. Si la réduction peut être faite en temps polynomial, vous avez prouvé que votre problème est NP-complet, si le problème est déjà en NP, car:

Ce n'est pas plus facile que le problème NP-complet, puisqu'il peut y être réduit en temps polynomial ce qui rend le problème NP-difficile.

Voir la fin de http://www.ics.uci.edu/~eppstein/161/960312.html pour en savoir plus.

moinudin
la source
2
+1 quelqu'un qui explique de manière compréhensible. au lieu de dire un tas de références à des mots-clés, je comprends à peine.
ColacX
22
La première phrase est à l'envers: vous devez réduire le problème NP-complet connu à votre propre problème. Cela montre que votre problème est au moins aussi difficile que le problème NP-complet connu. La partie (b) est également incorrecte: si vous avez trouvé la réduction, vous savez déjà que votre problème est NP-difficile; la seule question est de savoir si c'est en NP du tout (certains problèmes, comme le problème d'arrêt, ne le sont pas). S'il est NP-dur et NP, alors il est NP-complet (c'est-à-dire que "NP-complete" est plus spécifique que "NP-hard").
j_random_hacker
1
Je ne dirais pas que a) conduit à une contradiction, puisque nous ne savons pas que P! = NP.
Chiel ten Brinke
8

Afin de prouver qu'un problème L est NP-complet, nous devons suivre les étapes suivantes:

  1. Prouvez que votre problème L appartient à NP (c'est-à-dire que, étant donné une solution, vous pouvez le vérifier en temps polynomial)
  2. Sélectionnez un problème NP-complet connu L '
  3. Décrivez un algorithme f qui transforme L 'en L
  4. Prouvez que votre algorithme est correct (formellement: x ∈ L 'si et seulement si f (x) ∈ L)
  5. Prouver que algo f s'exécute en temps polynomial
Albert s
la source
7

Premièrement, vous montrez que cela réside dans le NP.

Ensuite, vous trouvez un autre problème dont vous savez déjà qu'il est NP complet et montrez comment vous réduisez polynomialement le problème NP Hard à votre problème.

Lagerbaer
la source
Non. Vous devez montrer que vous pouvez passer d'un problème NP complet à votre problème NP pour prouver l'exhaustivité de NP ET prouver qu'il s'agit d'un problème NP. NP hard n'entre pas en jeu, à moins que vous ne puissiez pas le prouver dans NP.
mrmemio29
6
  1. Familiarisez-vous avec un sous-ensemble de problèmes NP Complete
  2. Prove NP Hardness: Réduisez une instance arbitraire d'un problème NP complet en une instance de votre problème. C'est le plus gros morceau de gâteau et où la familiarité avec les problèmes NP Complete paie. La réduction sera plus ou moins difficile en fonction du problème NP Complete que vous choisissez.
  3. Prouvez que votre problème est en NP: concevez un algorithme qui peut vérifier en temps polynomial si une instance est une solution.
UmNyobe
la source