Aufgabe $3(10$ Punkte, NP$-$Vollst$$ndigkeit $-$ Set$-$Cover$)$

Betrachten Sie das Set$-$Cover Problem: Gegeben eine endliche Menge $M,$ endlich

viele Teilmengen $S_1,S_2,$dots,$S_n$ von $M$ und kinN. Gibt es unter den $n$ Mengen $S_i$

h$$chstens $k$ so$,$ dass deren Vereinigung gleich $M$ ist?

Zeigen Sie, dass dieses Problem NP$-$vollst$$ndig ist. $($Hinweis: Denken Sie an Vertex$-$

Cover aus der Vorlesung.$)$