Le problème de couverture exact NP-Dury en cas de restriction sur la taille?

Question

Le problème exact de couverture avec des restrictions sur la taille est:

Saisir: Étant donné un ensemble $ u = {1,2, ldots, n } $ et une collection de $ c $ de sous-ensembles de $ u $.

Question: Y a-t-il une sous-collection $ c ^ star $ de $ c $ tel que

• L'intersection de deux sous-ensembles distincts dans $ c ^ star $ est vide;
• Le syndicat des sous-ensembles dans $ c ^ star $ est $ u $; et
• La taille de tout ensemble $ s in c ^ star $ est au plus $ log_2 n $, ie, $ | s | leqslant log_2 n $ pour tous les $ s in c ^ star $.

Ce problème est-il NP-dur?