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

Question

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

Answer 1

Pour montrer la NP-complétude:

1) montrer que c'est dans NP.

Qui est, compte tenu de certaines informations C, vous pouvez créer un algorithme V qui va vérifier pour chaque entrée X si X est dans votre domaine ou non.

L'algorithme V doit s'exécuter en temps polynomial.

Par exemple:

Prouver que le problème du vertex couvre (qui est, pour un graphe G, a-t-elle d'un vertex cover set de taille k tel que chaque arête de G possède au moins un sommet dans la couverture de jeu?) est dans NP:

• notre entrée X est un graphe G et un nombre k (ce qui est de la définition du problème)
• Prendre nos informations C à "toute éventuelle sous-ensemble de sommets d'un graphe G de taille k"
• Ensuite, nous pouvons écrire un algorithme V que, compte tenu de G, k et C, sera de retour si l'ensemble de sommets est un vertex cover pour G ou pas, en temps polynomial.

Alors, pour tout graphe G, s'il existe quelques "possible sous-ensemble de sommets de G de taille k" qui est un vertex cover, alors G est dans NP.

Remarque: nous N'avons PAS besoin de trouver C en temps polynomial. Si nous pouvions, le problème serait en P.

Remarque: l'Algorithme V devrait fonctionner pour TOUS G, pour CERTAINS C. Pour chaque entrée il doit EXISTER des informations qui pourraient nous aider à vérifier si l'entrée est dans le domaine du problème ou pas. Qui est, il ne devrait pas être une entrée où l'information n'existe pas.

2) Prouver qu'il est NP-dur.

Il s'agit d'obtenir un connu NP-complets problème SAT (l'ensemble des expressions booléennes dans la forme "(A, B OU C) ET (D OU E OU F) ET ..." où l'expression est satisfiable (ie il existe certains paramètres de ces booléens qui rend l'expression du vrai).

Puis réduire le NP-complets problème à votre problème en temps polynomial.

Qui est, compte tenu de certaines d'entrée X pour SAT (ou quel que soit NP-complet problème que vous utilisez), créer une entrée de Y pour votre problème tel que X est à la SAT si et seulement si Y est dans votre problème. La fonction f:X -> Y doit s'exécuter en temps polynomial.

Dans l'exemple ci-dessus, l'entrée Y serait le graphe G et la taille d'un vertex cover k.

Pour une preuve complète, vous devez prouver à la fois:

• que X est ASSIS => Y dans votre problème
• et Y dans votre problème => X à la SAT.

marcog de répondre a un lien avec plusieurs autres NP-complet problèmes que vous pourriez réduire votre problème.

Answer 2

Vous avez besoin de réduire un problème NP-Complet de problème pour le problème que vous avez. Si la réduction se fait en temps polynomial, alors vous avez prouvé que votre problème est NP-complet, si le problème est déjà dans NP, parce que:

Il n'est pas plus facile que le NP-complet de problème, car il peut être réduit en temps polynomial qui rend le problème NP-Dur.

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

Answer 3

Tout d’abord, vous montrez qu’il s’agit de NP.

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