Riduzione del karp da problemi di ottimizzazione ai problemi decisionali

Question

Quando si considerano riduzioni di cucine, le versioni decisionali e ottimizzazione dei problemi sono il tempo polinomiale riducibile l'uno con l'altro.

Concentrandosi sulle riduzioni dei cuochi, esiste una riduzione del karp naturale dalla versione decisionale di un problema alla versione di ottimizzazione.Anche il Converse è vero?

Answer 1

Grazie a commenti di Yuval Filmus, capisco che la mia domanda non ha senso come riduzioni del KARP sono definite per problemi decisionali.Poiché le riduzioni dei cuochi consentono più Freeness, ha senso parlare di una riduzione del cuoco da un problema di decisione a un problema di ottimizzazione, ma questo non è vero per la riduzione del karp.