Quanto è difficile decidere se esiste un rigoroso miglioramento di una determinata soluzione di un problema di completamento NP?

Question

Prendi il problema della copertura impostata come esempio. Quando chiediamo se esiste una serie di dimensioni K che copre tutti gli elementi, il problema è NP-completo. Ora se lo chiediamo, per un determinato set $ S $ di dimensioni $ k $, se esiste un altro set che copre strettamente più elementi di $ S $ fa. Questo problema è ancora completo NP?

Per essere più chiaro, pensiamo al problema di copertura impostata come un problema di ottimizzazione: qual è il numero massimo di elementi che possono essere coperti da $ k $ imposta. La versione decisionale è: ci sono $ k $ set che coprono almeno $ m $ elementi? (dove $ m $ fa parte dell'input e la versione che stavi dicendo è semplicemente il caso speciale quando $ m = n $). Ora il problema è, per $ k $ Dati set (come parte dell'input), esistono $ k $ Altri set che coprono rigorosamente più elementi del $ k $ Dai set lo fanno.