Question

p_np
independent_set
set_cover

בשאלה זו נניח כי P̸=NP\text{P} \neq \text{NP}. עבור כל שפה מהשפות הבאות, קבע האם היא ב-P\text{P} או לא.

הערה: בכל הסעיפים הבאים, CiC_i, מסמן קבוצה, ו-kk מסמן מספר טבעי.

1. }\}קיימות kk קבוצות מתוך (C1,,Cm)(C_1, \dots, C_m) שחיתוכן ריק L1={(C1,,Cm,k):L_1 = \{(C_1, \dots, C_m, k) :

2. }\}קיימות kk קבוצות מתוך (C1,,Cm)(C_1, \dots, C_m) שכל זוג ביניהן זרותL2={(C1,,Cm,k):L_2 = \{(C_1, \dots, C_m, k) :

3. }\}קיימות kk קבוצות מתוך (C1,,Cm)(C_1, \dots, C_m) שאיחודן מכיל קבוצה אחרת L3={(C1,,Cm,k):L_3 = \{(C_1, \dots, C_m, k) :

4. }\}קיימות kk קבוצות מתוך (C1,,Cm)(C_1, \dots, C_m) שאיחודן מוכל בקבוצה אחרתL4={(C1,,Cm,k):L_4 = \{(C_1, \dots, C_m, k) :

1

Answers

1. נראה ש-L1/PL_1 \notin \text{P} על ידי רדוקציה מ-SC\text{SC}:

f([n],S1,,Sm,k)=([n]S1,,[n]Sm,k)f([n], S_1, \dots, S_m, k) = ([n] \setminus S_1, \dots, [n] \setminus S_m, k)

נשים לב שהקבוצות בפלט מייצגות את האיברים שהקבוצות בקלט לא מכסות. נשים לב שעבורI[n]I \subseteq [n] בגודל kk מתקיים ש-

iI([n]Si)=[n]iISi=    iISi=[n] \bigcup_{i \in I} ([n] \setminus S_i) = [n] \setminus \bigcup_{i \in I}S_i = \emptyset \iff \bigcup_{i \in I} S_i = [n]

ולכן ([n],S1,,Sm,k)SC    ([n]S1,,[n]Sm,k)L1([n], S_1, \dots, S_m, k) \in \text{SC} \iff ([n] \setminus S_1, \dots, [n] \setminus S_m, k) \in L_1.

2. ראו תשובה.

1. נראה ש-L3/PL_3 \notin \text{P} על ידי רדוקציה מ-SC\text{SC}:

f([n],S1,,Sm,k)=(S1{n+1},,Sm{n+m},[n],k)f([n], S_1, \dots, S_m, k) = (S_1 \cup \{n + 1\}, \dots, S_m \cup \{n + m\}, [n], k)

כלומר לכל קבוצה מקורית הוספנו איבר ששייך רק אליה ובנוסף הוספנו קבוצה שמכילה את כל האיברים 1 עד nn.

נשים לב שעבורI[n]I \subseteq [n] בגודל kk מתקיים ש-

iISi=[n]    [n]iI(Si{n+i}) \bigcup_{i \in I} S_i = [n] \implies [n] \subseteq \bigcup_{i \in I} (S_i \cup \{n + i\})

מצד שני, אם קיימות kk קבוצות בפלט שאיחודן מכיל קבוצה אחרת אז הוא חייב להכיל את [n][n] וזאת מכיוון שלכל קבוצה אחרת יש איבר ששייך רק אליה. ולכן עבורI[n]I \subseteq [n] בגודל kk מתקיים ש-

[n]iI(Si{n+i})    iISi=[n] [n] \subseteq \bigcup_{i \in I} (S_i \cup \{n + i\}) \implies \bigcup_{i \in I} S_i = [n]

4. נשים לב שאיחוד של kk קבוצות מוכל בקבוצה אחרת אמ"מ היא מכילה כל קבוצה בנפרד ואת זה אפשר לוודא ביעילות. כלומר L4PL_4 \in \text{P}.

1
Feedback