Comment sont tous les problèmes NP complets similaires?

cs.stackexchange https://cs.stackexchange.com/questions/3226

Question

Je lis quelques preuves qui prouvent un problème donné est NP complet. La technique a la preuve en suivant les étapes.

  1. Prouver que problème actuel est NP, à savoir, étant donné un certificat, prouver que l'on peut vérifier en temps polynomial.
  2. Prenez problème NP-complet connu (appel "Easy") et réduire tous de c'est des cas quelques cas de problème donné (appel "Difficile"). Notez que c'est pas nécessairement 1:. 1 mapping
  3. Prouver que la réduction ci-dessus peut être fait en temps polynomial.

Tout est bien ici. Est-ce droit de savoir « si vous pouvez résoudre tout problème NP-complet en temps polynomial, alors tous les problèmes NP-complets peuvent être résolus en temps polynomial »?

Si oui, comme ci-dessus technique de preuve, disons problème « Easy » peut être résolu en temps polynomial, comment cela implique « dur » peut être résolu en temps polynomial? Qu'est-ce que j'oublie ici? Ou est-ce vrai, ce problème « dur » peut être réduit au problème « facile » aussi?

Était-ce utile?

La solution

Votre question semble provenir du fait que vous n'êtes pas immédiatement convaincu que le problème actuel ne peut pas être plus difficile. Le problème actuel ne peut pas être plus difficile que tout problème NP-complet, car il est dans NP.

Si vous voulez être convaincu que la notion de NP-complet existe même (à savoir que vous pouvez réduire quoi que ce soit dans NP à un problème NP-complet), vous devriez étudier la Cook-Levin théorème qui stipule que SAT est NP-complet.

Depuis NP-complet indique quelque chose d'être la cible d'une réduction de aucun problème dans NP, la preuve fonctionne en encodant la machine de Turing qui était le vérificateur du problème d'origine comme une formule. Cette formule est satisfiable si et seulement s'il existe une entrée qui permet à la machine de Turing accepter. Vous pourriez en principe utiliser cette preuve pour réduire votre problème actuel de SAT, et après cela à tous les autres problèmes NP-complets par transitivité de la réduction du temps polynomiale.

(fait, je voulais simplement ajouter un lien vers le théorème Cook-Levin dans un commentaire, mais ceci est mon premier post StackExchange et je pense qu'il ne me laisse pas encore de commentaire.)

Autres conseils

Vous êtes confus par la direction de la réduction. Alors laissez-moi vous expliquer comment argumenter.

Vous avez une langue, disons $ L $ et que vous voulez montrer qu'il est NP-complet. Tout d'abord vous montrer que est en effet dans NP, à savoir, en trouvant un bon certificat. Ainsi, il vous reste en montrant la NP-dureté. Cela peut être fait en réduisant un langage NP-complet $ L_ \ texte {PNJ} $ votre langue $ L $, par un polynomial beaucoup-une réduction . Cela signifie que vous définissez une fonction polynomial, qui mappe oui-instances du texte de $ L_ {PNJ} $ à oui-instances de $ L $, et que les cartes non-instances de texte $ L_ \ {PNJ} $ pour non-cas de $ L $.

Par transitivité de nombreux polynomial-une réduction, toutes les langues NP peut maintenant être réduit à $ L $ ( prendre un détour par le texte $ L_ {PNJ} $). D'autre part, s'il existe un algorithme polynomial déterministe $ A $ qui décide $ L $, nous pouvons décider de toutes les langues NP en temps polynomial, en réduisant d'abord à $ L $ et demander $ A $.

Il semble que vous venez de penser dans la mauvaise direction. Le problème que vous avez appelé « facile », peut être résolu avec l'aide de la réduction et le problème que vous appelez « dur ». Tout d'abord, cela est étrange terminologie trompeuse, et deuxièmement, il devrait probablement être l'inverse.

Étant donné un ensemble $ A \ subset \ mathbb R $, comment pouvez-vous montrer que $ a $ est un plus grand élément de l'ensemble $ A $? Il y a deux étapes:

  1. Montrer que $ a \ in A $.
  2. Montrer que pour tout $ b \ en A $, $ b \ leq a $.

Si $ a, b $ sont les plus grands éléments de l'ensemble $ A $, puis en appliquant la condition 2 deux fois (pour $ a et $ b $) vous obtenez un $ \ leq b \ leq a $. Dans $ \ mathbb R $, cela signifie $ a = b $ et un ensemble ne peut avoir qu'un seul plus grand élément.

remplacer $ \ mathbb R $ par $ A ^ {\ ast} $ et $ \ leq $ par l'existence de la réduction du temps polynomiale. Pour montrer que $ L $ est NP-complet, il y a des étapes:

  1. Montrer que $ L \ in \ mathsf {NP} $.
  2. Montrer que pour tout $ L \ 'en \ mathsf {NP} $, $ L \ leq L $. Cette condition est appelée NP-dureté.

Si $ L, M $ sont deux langues NP-complets, puis en appliquant deux fois la condition 2 vous obtenez $ L \ leq M \ leq L $. Ce qui signifie que les problèmes sont équivalents: si vous êtes en mesure de résoudre $ L $, alors vous pouvez résoudre $ M $ et vice-versa. Contrairement à reals, il est peut-être vrai que $ L \ NEQ M $. Soit $ L \ sim M $ moyenne $ L \ leq M leq L $ de. Vous pouvez afficher ceci est une relation d'équivalence.

Exercice.

On suppose que $ M $ est NP-complet, et que $ L \ sim M $. Montrer que $ L $ est NP-complet.

  1. Montrer que $ L \ in \ mathsf {NP} $.

      

    Depuis $ M $ est en NP, et $ L \ leq M $, une machine reconnaissant $ L $ peut simplement utiliser la réduction.

  2. Montrer que pour tout $ L \ 'en \ mathsf {NP} $, $ L \ leq L $.

      

    Depuis M $ est NP-dur, $ L \ leq M $. Puisque nous savons M $ de leq L $ de, par transitivité $ L \ leq L $.

Par conséquent, si deux langues sont NP-complets, ils sont équivalents. Si une langue est équivalent au langage NP-complet, il est NP-complet.

Il semble y avoir deux idées fausses ici.

  1. « Easy » et « dur »: si quoi que ce soit, il est l'autre sens. Le problème donné est « facile » (nous ne savons pas sa complexité), l'autre est connu être dur.
  2. "réduire tous de celui-ci de cas quelques cas de problème donné": l'accent est trompeur. Il est important de ne pas la taille de la plage de valeurs de la réduction est. Ce qui est essentiel est que les conserves de réduction si l'instance est une instance OUI. En d'autres termes, l'instance du problème NPC est une instance OUI si et seulement si son image de réduction est une instance OUI pour le problème donné.

Alors, ce que vous faites est de montrer que vous pouvez résoudre le problème difficile en cartographiant ses instances aux instances de celle donnée (en temps polynomial) et résoudre ceux-ci. Par conséquent, le problème difficile de ne pas peut être plus difficile que celle donnée. De manière équivalente, le problème donné est au moins aussi dur que le problème difficile. Quod erat demonstrandum.

Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange
scroll top