Tous les problèmes NP se réduisent à des problèmes NP-complets: alors comment les problèmes NP ne peuvent-ils pas être NP-complets?

10

Mon livre dit ceci

  • Si un problème de décision B est dans P et A se réduit à B, alors le problème de décision A est dans P.
  • Un problème de décision B est NP-complet si B est dans NP et pour chaque problème dans A dans NP, A se réduit à B.
  • Un problème de décision C est NP-complet si C est dans NP et pour certains problèmes B NP-complets, B se réduit à C.

Donc mes questions sont

  1. Si B ou C est en NP-complet et que tous les problèmes en NP se réduisent à un problème NP-complet, en utilisant la première règle, comment un problème NP ne peut-il pas être NP complet?
  2. Si A se réduit à B, B se réduit-il à A?
complexity-theory np-complete decision-problem rubixibuc
la source
2
Fait intéressant lié à votre n ° 1: si P n'est pas égal à NP, nous savons qu'il doit y avoir des problèmes NP qui ne sont pas NP-complets (c'est le théorème de Ladner. Voir NP Intermédiaire ). Ce qui est étrange, c'est que nous ne sommes pas sûrs de problèmes de calcul courants qui entrent dans cette catégorie. Le problème utilisé dans le théorème de Ladner est construit artificiellement pour prouver le théorème, mais est pratiquement sans importance.
Lucas Cook
4
@Lucas, Factoring et GraphIso sont supposés être NPI, voir aussi ceci .
Kaveh
@Kaveh: Belle liste de candidats NPI, merci! Pour clarifier, je disais que nous ne sommes pas "sûrs" d'un problème naturel de NPI avec la même certitude que les problèmes de Ladner. Autrement dit, si , les seuls problèmes NPI connus pour certains sont artificiels liés à la hiérarchie de Ladner. P≠NP
Lucas Cook

Réponses:

13

Si A se réduit à B, B se réduit-il à A?

Non. Pour un exemple vraiment artificiel, tout problème calculable possible A est réductible au problème d'arrêt: il suffit de passer en entrée l'algorithme qui résout le problème A mais avec un while(true)virement de bord à la fin après le vrai ou le faux cas. Cependant, nous savons que le problème de l'arrêt n'est pas calculable, il ne peut donc pas être réduit à un tel algorithme A.

L'idée de base est que s'il y a une réduction de A à B, vous pouvez apprendre que B est au moins aussi difficile à résoudre que A et nécessite un algorithme au moins aussi puissant.

Donc, si un problème A se réduit à un problème facile B, alors nous pouvons déduire A est facile (puisque la réduction nous donne l'algorithme efficace) et si un problème difficile A réduit à un problème B, nous pouvons déduire que B est également difficile ( car si B était facile, alors A devrait l'être aussi). Cependant, il est toujours possible de faire une réduction stupide d'un problème facile à un problème difficile, mais dans ce cas, nous ne pouvons en tirer aucune conclusion.

hugomg
la source
8

Si B ou C est dans NP Complete et que tous les problèmes dans NP se réduisent à un problème NP Complete, en utilisant la première règle, comment un problème NP ne peut-il pas être NP complet?

La première règle concerne les problèmes de P. Elle n'a rien à voir avec l'exhaustivité de NP. Si le problème A est NP Complete et que le problème B se réduit à A, cela ne signifie pas que B est NP Complete.

Si A se réduit à B, B se réduit-il à A?

Pas généralement, non.

sepp2k
la source
"Pas en général, non.", Pourquoi? Une petite explication pourrait également être utile pour les débutants. Une explication de votre première réponse doit également être fournie.
nbro
-1

Je n'ai que l'idée de base concernant les problèmes NPC et NP. Mais tout ce que je veux dire, c'est "Si A est réduit à B, alors B est réduit à A?"

Considérez simplement un ensemble A contenant {2,3,4,5} éléments et un ensemble B contenant {3,4}. Ainsi, A peut être réduit à B. Mais B ne peut pas être réduit à A. Au lieu de cela, B peut être étendu à A si B gagne {2,5} éléments.

Mais si A et B ont la même chose. alors A peut être réduit à B ou B peut être réduit à A.

Naveen CS
la source
Ce n'est pas du tout la bonne idée de réduction. La réduction ne concerne pas les ensembles qui gagnent ou perdent des éléments. Il s'agit plutôt de pouvoir convertir une instance d'un problème en un autre à l'aide d'une machine / algorithme de Turing.
jmite
D'accord. Donc, si un problème est réduit à un autre en utilisant un algorithme, il n'est pas possible de le récupérer à partir de la sortie réduite en utilisant à nouveau ce même algorithme.
Naveen CS
1
Je ne suis pas totalement sûr de ce que vous voulez dire, mais je pense que ce n'est pas possible. Si je ne me trompe pas, ces réductions peuvent être de plusieurs pour un. A se réduit à B si un nombre d'appels polynomial à un sous-programme résolvant B permet de résoudre A en temps polynomial. Différentes instances de A pourraient invoquer un appel la même instance de B.
jmite
2
La question concerne les problèmes de décision, pas les ensembles. Comment est-il utile de regarder les ensembles? Utiliser le mot «réduit» pour signifier qu'un ensemble est un surensemble d'un autre n'est même pas une terminologie courante.
Gilles 'SO- arrête d'être méchant'