KARP réduction des problèmes d'optimisation aux problèmes de décision

Question

Lorsque vous envisagez des réductions de cuisson, les versions de décision et d'optimisation des problèmes sont la durée polynomiale réduite les unes aux autres.

Se concentrer sur les réductions de cuisson, il existe une réduction naturelle de KARP de la version de décision d'un problème à la version d'optimisation.Est l'inverse aussi vraie?

Answer 1

Merci à des commentaires de Yuval Filmus, je comprends que ma question n'a pas de sens, car les réductions de KARP sont définies pour les problèmes de décision.Étant donné que les réductions de cuisson permettent plus de pente, il est logique de parler d'une réduction de cuisson d'un problème de décision à un problème d'optimisation, mais cela n'est pas vrai pour la réduction Karp.