Question

classification_p_np
vertex_cover
independent_set

בהנחה ש P̸=NPP \neq NP קבעו עבור כל שפה האם היא ב-PP. הוכיחו את תשובתכם.

1. }\}קיים ל-GG כיסוי בצמתים בגודל kk או קבוצה בלתי תלויה בגודל kk L1={(G,k):L_1 = \{(G,k) :

2. }\}קיים ל-GG כיסוי בצמתים בגודל kk וגם קבוצה בלתי תלויה בגודל kk L2={(G,k):L_2 = \{(G,k) :

3. }\}GG קשיר וקיים ל-GG כיסוי בצמתים בגודל kk שהוא גם קבוצה בלתי תלויה L3={(G,k):L_3 = \{(G,k) :

1

Answers

נניח בה"כ ש-kVk \leq |V|.

1. נראה ש-L1NPCL_1 \in \text{NPC} על ידי רדוקציה מ-IS:

f(G,k)=(GH,k+1)f(G, k) = (G \cup H, k + 1)

כאשר HH הוא גרף מלא על k+2k + 2 צמתים שאינם ב-GG. נשים לב שב-GHG \cup H לא קיים כיסוי בגודל k+1k + 1 וקיימת קבוצה בת"ל בגודל k+1k + 1 אמ"מ קיימת קבוצה בת"ל בגודל kk ב-GG.

2. נראה ש-L2NPCL_2 \in \text{NPC} על ידי רדוקציה מ-VC:

f(G,k)=(GH,k)f(G, k) = (G \cup H, k)

כאשר HH הוא גרף ללא קשתות על kk צמתים שאינם ב-GG. נשים לב שב-GHG \cup H תמיד קיימת קבוצה בת"ל בגודל kk וקיים כיסוי בצמתים בגודל kk אמ"מ קיים כיסוי כזה ב-GG.

3. נראה ש-L3PL_3 \in P:

טענה:

קיימת קבוצה כזאת אמ"מ GG גרף דו צדדי ומספר הצמתים בצד אחד שלו קטן או שווה ל-kk.

הוכחה:

אם קיימת קבוצה בת"ל שהיא גם כיסוי בצמתים בגודל kk, II, אז נשים לב ש-VIV \setminus I גם קבוצה בת"ל או ש-II לא כיסוי.

מצד שני, אם GG הוא גרף דו צדדי כך שצד אחד שלו בגודל קטן או שווה ל-kk, LL, אז LL כיסוי בצמתים או ש-GG אינו דו צדדי.

נשים לב שאת התכונה הנ"ל קל לבדוק בזמן פולינומי.

1
Feedback