J'ai cette confusion à l'esprit au sujet des réductions liées aux problèmes NP complets. Disons que nous avons 2 problèmes R et S pas connus pour être dans NP. Maintenant, si nous avons une réduction de temps polynomiale d'un problème complet de NP bien connu à R et nous avons aussi une réduction de temps polynomiale de S au problème complet de NP .. ce qui peut être dit sur les problèmes R et S. NP dur?NP complète des réductions
Si un problème NP-complet réduit en temps polynomial à R, alors tous les problèmes de NP diminuent également; par conséquent, R est NP-Hard.
Si S se réduit à un problème NP-complet, alors S est NP.
Aucun des deux n'est nécessairement NP-complet; nous ne savons pas si R est NP (peut-être c'est indécidable) ou si S est NP-Hard (peut-être c'est trivial?).
Merci pour cela, j'ai un autre doute dans mon esprit laisse dire un problème L qui est dans NP est réduit à un problème L '.. alors ce qui peut être dit sur le problème L' – user2044593
@ user2044593 Rien de substance: L'mai être indécidable, NP-Complet, NP mais pas NP-complet (en supposant P! = NP), ou P. Notez que tout problème se réduit à lui-même. Même si vous jetez ce cas trivial, il n'est pas difficile de trouver des problèmes L 'tels que L' et L sont résolus par des algorithmes qui font essentiellement la même chose. – Patrick87
Merci pour la clarification! – user2044593
Je vote pour clore cette question hors-sujet parce qu'il ne s'agit pas de programmation mais de maths. –