TROUVE un ensemble de frappe de taille n / 2 NP-du-dur?

Question

Dans un problème de jeu, on nous donne une collection E de sous-ensembles de V et nous voulons trouver le plus petit sous-ensemble H de V qui se croit (Hits) chaque ensemble en E.

Dans la version de décision du problème, on nous demande s'il existe un ensemble de frappe H de taille au plus k.

Ce problème est connu pour être du NP. Cependant, je me demande si le problème est encore du NP quand on demande s'il existe un ensemble de frappe dont la taille est strictement inférieure à N / 2, c'est-à-dire au plus n / 2 - 1, (où n est la taille de v) .

Je travaille actuellement sur un autre problème et je suis convaincu que le problème est du NP-dur. J'essaye donc de trouver une réduction. Je me suis rendu compte que si le problème ci-dessus est NP-dur, alors j'ai terminé.

Toute aide est appréciée.