np/p
Von: , Frage gestellt am Mi, 1. Jun 2005
hallo, vielleicht kann mir jemand bei folgendem beweis helfen..
Sei S eine endliche Menge und C eine Menge von Teilmengen von S. SET
SPLITTING ist das Problem zu entscheiden, ob es eine Partition von S in zwei Teilmengen
S1 und S2 gibt, sodass jede Menge aus C sowohl mit S1 als auch mit S2 mindestens ein
Element gemeinsam hat.
Überlege, ob das Problem SET SPLITTING in P liegt oder NP-vollständig ist. Beweise
Deine Antwort.
danke