À quel point est-il difficile de décider s'il existe une amélioration stricte d'une solution donnée d'un problème NP-Complete?

Question

Prenez le problème de la couverture définie comme exemple. Lorsque nous demandons s'il y a un ensemble de taille K qui couvre tous les éléments, le problème est NP-complete. Maintenant, si nous demandons, pour un ensemble donné $ S $ de taille $ k $, s'il existe un autre ensemble qui couvre strictement plus d'éléments que $ S $ Est-ce que. Ce problème est-il encore NP-Complete?

Pour être plus clair, considérons le problème de la couverture de set comme un problème d'optimisation: quel est le nombre maximum d'éléments qui peuvent être couverts par $ k $ ensembles. La version de décision est: sont là $ k $ les ensembles couvrent au moins $ m $ éléments? (où $ m $ fait partie de l'entrée, et la version que vous disiez est simplement le cas spécial lorsque $ m = n $). Maintenant, le problème est, pour $ k $ des ensembles donnés (dans le cadre de l'entrée), existe-t-il $ k $ D'autres ensembles qui couvrent strictement plus d'éléments que le $ k $ Les ensembles donnés font.