יהיו G 1 = (V, E 1), G 2 = (V, E 2) שני גרפים לא מכוונים, המוגדרים על אותה קבוצת קודקודים V. נסמן ב- (G 1, G 2…

יהיו $G_1 = (V, E_1)$, $G_2 = (V, E_2)$ שני גרפים לא מכוונים, המוגדרים על אותה קבוצת קודקודים $V$. נסמן ב-$\alpha(G_1, G_2)$ את גודלה של קבוצת הקודקודים המקסימאלית המהווה קבוצה בלתי-תלויה גם ב-$G_1$ וגם ב-$G_2$. נגדיר את השפה הבאה: $\text{MAX-Common-IS} = \{ \langle G_1, G_2, k \rangle \mid \alpha(G_1, G_2) = k \}$. א. הוכיחו כי $\text{MAX-Common-IS}$ היא $NP$-קשה. (10 נק') ב. הוכיחו כי $\text{MAX-Common-IS}$ היא $coNP$-קשה. (10 נק') ג. האם הטענה הבאה נכונה ? הוכיחו תשובתכם. (6 נק') טענה: אם $MAX\text{-}Common\text{-}IS \in coNP$ אז $NP = coNP$. הקיפו: הטענה נכונה \ הטענה שגויה