Si un problème X (problème de décision) est connu pour être NP-complet et qu'il s'est avéré être réduit au problème Y, pouvez-vous alors dire que le problème Y est NP-complet?

Si un problème X (problème de décision) est connu pour être NP-complet, et qu'il s'est avéré être réduit au problème Y en polynomialtime, pouvez-vous alors dire que le problème Y est NP-complet?Si un problème X (problème de décision) est connu pour être NP-complet et qu'il s'est avéré être réduit au problème Y, pouvez-vous alors dire que le problème Y est NP-complet?

Ma première pensée était, non, problème Y doit être montré qu'il est dans NP. Mais après réflexion, si X est réduit à Y, Y est déjà considéré comme NP-Complet. Maintenant, je suis confus ... toute aide serait appréciée.

Source

2010-11-02 Mr. X

Je pense que vous l'avez eu la première fois. Si nous pouvons réduire n'importe quel problème connu à un autre problème complet NP, ce problème est également NP. – Jim

de wiki: "... des milliers d'autres problèmes ont été montrés être NP-complets par des réductions d'autres problèmes précédemment montrés être NP-complets; ... donc je dirais que" oui "est la réponse? –

Par définition, Y est "NP-difficile". Un problème NP-difficile est celui qui peut être utilisé pour résoudre n'importe quel problème dans NP, y compris le problème NP-complet. Cependant, un problème NP-difficile n'est pas nécessairement NP. – gnasher729

Argumentum par contrarium:

Si X ∈ NP et X ⇔ Y et Y ∉ NP alors X ∉ NP.

Source

2010-11-02 02:51:45 msw

Problème X - Pas sûr
Problème Y - Dans NP

Pour prouver X est dans NP, vous montrer que vous pouvez suivre des mesures pour réduire tous les problèmes dans X à un problème dans Y. Alors, vous savez que le Le problème X est au moins aussi difficile que le problème Y équivalent.

donc pas, vous devez commencer par Y, puis réduire à X.

Source

2010-11-02 02:55:20

SAT peut être résolu en un seul appel à tous, mais cela ne veut pas dire que tout est dans NP.

Source

2010-11-02 06:13:26 Charles

Oui, c'est correct. Vous pouvez réduire votre problème en temps polynomial à tout problème NP complet déjà connu, mais cela est considéré comme une tâche très difficile. Donc, à la place, vous choisissez un problème déjà complet NP et le réduire à votre problème et aussi montrer qu'il est en NP, alors votre problème sera NP complète.

Source

2013-12-01 00:00:25 happs

Pas encore, vous aurez besoin de quelques étapes

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

Prouver votre problème L appartient NP (qui est une solution donnée que vous pouvez le vérifier en temps polynomial)
Sélectionnez un problème NP-complet connu L «
Décrire un algorithme f qui transforme L » en L
Pro ve que votre algorithme est correct (formellement: x ∈ L si et seulement si f (x) ∈ L)
Prouver que algo f fonctionne en temps polynomiale

Jusqu'ici, vous avez pas 2,3, 4
Vous devez toujours montrer que la réduction est polynomiale (étape 5)
Et que le problème appartient à NP (étape 1), c'est-à-dire qu'une solution peut être vérifiée en temps polynomial.

Source

2016-09-01 00:53:02

Si un problème X (problème de décision) est connu pour être NP-complet et qu'il s'est avéré être réduit au problème Y, pouvez-vous alors dire que le problème Y est NP-complet?

Répondre

Questions connexes